多重背包模板

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

const int MAXW = 10010;

int main() {
    int n, W;
    cin >> n >> W;

    int dp[MAXW] = {};
    for (int i = 0; i < n; i++) {
        int w, v, s;
        cin >> w >> v >> s;

        // 二进制拆分：把 s 个拆成 1,2,4,...,剩余
        for (int k = 1; s > 0; k <<= 1) {
            int take = min(k, s);
            int tw = take * w, tv = take * v;
            for (int j = W; j >= tw; j--)
                dp[j] = max(dp[j], dp[j - tw] + tv);
            s -= take;
        }
    }

    cout << dp[W] << endl;
    return 0;
}

📖 要点说明

• 多重背包 = 01背包 + 二进制拆分
• 把 s 个物品拆成 log s 组，每组按01背包处理
• 拆分：1, 2, 4, ..., 剩余

⚠️ 常见错误

• 拆分后仍正序遍历（应倒序，按01背包）
• 忘取 min(k, s) 处理最后一组
• 不拆分直接枚举数量会超时