题解 | 【模板】完全背包

问题1：dp[i]表示背包最大容量为i的情况下，能装下的最多价值。

由于完全背包中，每个物品可以选择无数次。一种比较简单的思路是，每一个物品都copy足够多次，多到单独选择任意一个物品都能够填满整个背包。这样将物品数量增加，将问题转换为0 1背包。但是这种思路会被卡。

另外的思路：考虑在0 1背包中，是如何保证物品只被选择一次呢？即重量3的物品在容量为10中能够被选择，是建立在其在容量为7时没有被选择。即转移方程中 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + b[i]);是将dp[i - 1]时的状态，即考虑前i - 1个物品时的状态下的值作为选择。在dp[i - 1]的所有状态中，都没有选择i物品。

如果理解了这一点，那么如何多次选择就很明显了，即将dp[i - 1]改为dp[i]既可。使用空间优化后的数组，仅仅需要将0 1背包中，之前从右往左的计算改为从左往右既可。

问题2：同理，dp[i]表示背包刚好装满i的情况下，能装下的最多价值。同样从左往右遍历既可。

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

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

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