python/TangDou/AcWing/BeiBao/2_dfs_int.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int n;    // 物品的数量
int m;    // 背包的体积上限
int w[N]; // 每个物品的价值
int v[N]; // 每个物品的重量，体积
/**
 * 功能：深度优先搜索
 * @param u  走到第u物品面前
 * @param r     剩余容量r
 * @return      可以获得的最大价值是多少
 */
int dfs(int u, int r) {
    // 如果出界了，返回0
    if (u == n + 1) return 0;
    // 如果不够装下，只能放弃
    if (v[u] > r) return dfs(u + 1, r);
    // 如果可以装下，可以选择要、还是不要
    return max(dfs(u + 1, r), dfs(u + 1, r - v[u]) + w[u]);
}

int main() {
    // 物品个数与背包容量
    cin >> n >> m;
    // 读入每个物品的体积和价值
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    // 深搜并输出结果~
    printf("%d\n", dfs(1, m));
    return 0;
}