python/TangDou/BeiBao/Teach/01_Dfs_JYH.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int n;          //物品的数量
int m;          //背包的容量上限
int w[N];       //每个物品的重量(价值)
int v[N];       //每个物品的体积
int dp[N][N];   //引入dp数组保存已经计算过的结果
/**
 * 功能：深度优先搜索+记忆化解决01背包
 * @param step  走到第step物品面前
 * @param r     剩余容量r
 * @return      可以获得的最大价值是多少
 */
int dfs(int step, int r) {
    //判断这种情况是否被计算过
    if (dp[step][r] > 0) return dp[step][r];

    //如果都出界了，返回0
    if (step == n + 1) return 0;
    //结果
    int res;
    //如果不够装下，只能放弃
    if (v[step] > r) res = dfs(step + 1, r);
        //如果可以装下，可以选择要、还是不要
    else res = max(dfs(step + 1, r), dfs(step + 1, r - v[step]) + w[step]);
    //保存结果
    dp[step][r] = res;
    return res;
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    //物品个数与背包容量
    cin >> n >> m;
    //读入每个物品的体积和价值
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    //深搜并输出结果
    cout << dfs(1, m) << endl;
    return 0;
}