【例86.4】 混合背包

解题思路

对每种物品使用旧数组到新数组转移。数量上限为P，若P=0则上限是M/w。对每个容量j枚举0～min(上限,j/w)件，更新old[j-kw]+kv，整种处理完再替换。

正确性说明

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

易错点

P=0表示无限，不是不能选；必须用旧数组避免多重限制失效。

复杂度

时间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, p;
        long long v;
        cin >> w >> v >> p;
        int limit = p == 0 ? M / w : min(p, M / w);
        vector<long long> next = dp;
        for (int j = 0; j <= M; j++)
            for (int k = 1; k <= limit && k * w <= j; k++)
                next[j] = max(next[j], dp[j - k * w] + k * v);
        dp.swap(next);
    }
    cout << dp[M] << "\n";
    return 0;
}