【例86.3】 完全背包问题

解题思路

完全背包每种可重复，dp含义同最大价值。容量从w向M升序更新，dp[j-w]允许已包含当前物品，从而可再放一件。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

与01背包方向相反；按本站样例输出max=前缀。

复杂度

时间O(NM)，空间O(M)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, N;
    cin >> M >> N;
    vector<long long> dp(M + 1);
    while (N--) {
        int w;
        long long v;
        cin >> w >> v;
        for (int j = w; j <= M; j++)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << "max=" << dp[M] << "\n";
    return 0;
}