题解 | 【模板】01背包

问题1：01背包经典问题。

dp[i][j]表示考虑前i个物品，背包最大容量为j的时候，能装下的最大价值。

转移方程：

if (a[i] <= j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);

由于dp[i]的变化只与dp[i - 1]相关，估可以考虑从右向左遍历，使用一维数组来节约空间。

最后返回dp[n - 1][v]既可。

问题2：01背包的简单变形

dp[i][j]表示考虑前i个物品，背包刚好装满j的时候，能装下的最大价值。

考虑两种情况：

当a[i] == j的时候，这个物品可以选，既dp[i][j] = max(dp[i - 1][j], b[i]);

当a[i] < j的时候，如果dp[i - 1][j - a[i]]不为0，则表示拿了 i 这个物品，能把j的容量拿满，

则dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);

如果为0的话，则表示拿了 i 这个物品，无法将j的容量拿满。所以无需处理。

当a[i]>j的时候，无需处理。

同理，可以考虑从右向左遍历，使用一维数组来节约空间。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, v;
    cin >> n >> v;
    vector<int> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    vector<int> dp(v + 1, 0);
    vector<int> dp2(v + 1, 0);


    for (int i = 0; i < n; i++) 
        for (int j = v; j >= 0; j--) 
            if (a[i] <= j)
                dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
    cout << dp[v] << '\n';

    for (int i = 0; i < n; i++) {
        for (int j = v; j >= 0; j--) {
            if (a[i] == j) {
                dp2[j] = max(dp2[j], b[i]);
            } else if (a[i] < j) {
                if (dp2[j - a[i]] != 0) dp2[j] = max(dp2[j], dp2[j - a[i]] + b[i]);
            }
        }
    }
    cout << dp2[v] << '\n';
}
// 64 位输出请用 printf("%lld")