0 - 1背包问题(从dfs开始理解，动态规划则水到渠成)

以前刚学背包的时候，直接干动态规划，总是觉得很奇怪，为什么要那么想，到底怎么想出来的，现在知道了，原来最原始思考都是从dfs过来的，我们想dfs的思路，就是动态规划转移方程的思路，写出dfs后，直接就可以按照dfs的代码将状态方程写出来了。希望对动态规划还没有理解的同学有所帮助！

dfs

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
// n是行数，m是背包大小
int w[N], v[N], n, m;

int dfs(int u, int s) {
    if(u >= n || s <= 0) {
        return 0;
    }

    int s1 = 0, s2 = 0;
    // 选当前的物品
    if(s >= v[u]) s1 += (w[u] + dfs(u + 1, s - v[u]));
    s2 += dfs(u + 1, s);
    return max(s1, s2);
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i ++) {
        cin >> v[i] >> w[i];
    }
    // 现在走到第u个位置，背包容量剩s
    cout << dfs(0, m);
    return 0;
}

加记忆化

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
// n是行数，m是背包大小
int w[N], v[N], n, m;
int dp[N][N];

int dfs(int u, int s) {
    if(dp[u][s] != -1) return dp[u][s];
    if(u >= n || s <= 0) {
        return 0;
    }
    // s1表示拿当前物品那个分支的值，s2表示不拿
    int s1 = 0, s2 = 0;
    // 选当前的物品
    if(s >= v[u]) s1 += (w[u] + dfs(u + 1, s - v[u]));
    s2 += dfs(u + 1, s);
    dp[u][s] = max(s1, s2);
    return max(s1, s2);
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i ++) {
        cin >> v[i] >> w[i];
    }
    for(int i = 0; i <= n; i ++) {
        for(int j = 0; j <= m; j ++) {
            dp[i][j] = -1;
        }
    }
    // 现在走到第u个位置，背包容量剩s
    cout << dfs(0, m);
    return 0;
}

动态规划

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
// n是行数，m是背包大小
int w[N], v[N], n, m;
int dp[N][N];

int dfs(int u, int s) {

    if(dp[u][s] != -1) return dp[u][s];

    if(u >= n || s <= 0) {
        return 0;
    }
    // s1表示拿当前物品那个分支的值，s2表示不拿
    int s1 = 0, s2 = 0;
    // 选当前的物品
    if(s >= v[u]) s1 += (w[u] + dfs(u + 1, s - v[u]));
    s2 += dfs(u + 1, s);
    dp[u][s] = max(s1, s2);
    return max(s1, s2);
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i ++) {
        cin >> v[i] >> w[i];
    }
    for(int i = n; i >= 0; i --) {
        for(int j = 0; j <= m; j ++) {
            if(j >= v[i]) dp[i][j] = dp[i + 1][j - v[i]] + w[i];
            dp[i][j] = max(dp[i][j], dp[i + 1][j]);
        }
    }
    // 现在走到第u个位置，背包容量剩s
    cout << dp[0][m];
    return 0;
}