二维数组二进制

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int N, W;
vector<ll> w, v, s;
vector<vector<ll>> dp;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> W;
    dp.resize(N + 1, vector<ll>(W + 1, 0));
    w.resize(N + 1); v.resize(N + 1); s.resize(N + 1);
    
    for(int i = 1; i <= N; i++){
        cin >> w[i] >> v[i] >> s[i];
    }
    
    for(int i = 1; i <= N; i++){
        // 修复黑洞：在拆分之前，先原封不动地把上一层 i-1 的所有状态继承到第 i 层
        for(int j = 0; j <= W; j++){
            dp[i][j] = dp[i-1][j];
        }
        
        for(ll k = 1; s[i] > 0; k <<= 1){
            ll c = min(k, s[i]);
            ll nw = c * w[i], nv = c * v[i];
            
            for(int j = W; j >= nw; j--){
                // 修复失忆症：这里的转移必须基于 dp[i] 自己！
                // 因为此时 dp[i] 已经包含了“当前物品之前拿过的包裹”的状态
                dp[i][j] = max(dp[i][j], dp[i][j - nw] + nv); 
            }
            s[i] -= c;
        }
    }
    cout << dp[N][W] << "\n";
    return 0;
}

二进制版本

#include <bits/stdc++.h>
using namespace std;
int dp[10005];
int main() {
    // 开启极限加速，应对可能的大量输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, W;
    cin >> n >> W;
    
    // 第1层循环：遍历每一类物品
    for (int i = 1; i <= n; i++) {
        int w, v, s;
        cin >> w >> v >> s;
        
        // 第2层循环：巧妙的二进制拆分（自动处理 1, 2, 4... 以及最后的余数包裹）
        for (int k = 1; s > 0; k = min(k * 2, s)) {
            
            // 第3层循环：标准的 01 背包倒序容量转移
            for (int j = W; j >= k * w; j--) {
                dp[j] = max(dp[j], dp[j - k * w] + k * v);
            }
            
            s -= k; // 拆分出一个包裹后，将对应件数扣除
        }
    }
    
    // 输出刚好不超过背包容量的最大价值
    cout << dp[W] << "\n";
    
    return 0;
}

最普通代码：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, W;
    cin >> N >> W;
    // w[i], v[i], s[i] 分别是第 i 类物品的重量、价值、可取上限
    vector<int> w(N+1), v(N+1), s(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i] >> s[i];
    }

    // dp[i][j] = 考虑前 i 类物品，总重量不超过 j 时的最大价值
    vector<vector<ll>> dp(N+1, vector<ll>(W+1, 0));

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            // 不拿第 i 类
            dp[i][j] = dp[i-1][j];
            // 尝试拿 k 件第 i 类
            for (int k = 1; k <= s[i] && k * w[i] <= j; k++) {
                dp[i][j] = max(dp[i][j],
                               dp[i-1][j - k * w[i]] + (ll)k * v[i]);
            }
        }
    }

    cout << dp[N][W] << "\n";
    return 0;
}

最佳代码，单调队列滑动窗口

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N), s(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i] >> s[i];
    }

    // dp[j] 表示容量 j 时的最大价值
    vector<ll> dp(W+1, 0);

    // 遍历每一类物品，单调队列优化多重背包
    for (int i = 0; i < N; i++) {
        int wi = w[i], vi = v[i], si = s[i];
        // 对每个余数 r = 0,1,...,wi-1 分别做一遍
        for (int r = 0; r < wi; r++) {
            deque<pair<ll,int>> dq;
            // 对 j = m*wi + r 进行枚举
            // 令 m 从 0 开始，j = m*wi + r ≤ W
            for (int m = 0, j = r; j <= W; m++, j += wi) {
                // 当前状态值：dp[j] - m*vi
                ll cur = dp[j] - (ll)m * vi;

                // 滑出队列边界：只保留窗口大小 si+1
                while (!dq.empty() && dq.front().second < m - si)
                    dq.pop_front();
                // 单调递减入队
                while (!dq.empty() && dq.back().first <= cur)
                    dq.pop_back();
                dq.emplace_back(cur, m);

                // 队首即为最大值 + 补偿回去 m*vi
                dp[j] = dq.front().first + (ll)m * vi;
            }
        }
    }

    cout << dp[W] << "\n";
    return 0;
}

二进制优化代码：

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

// proc：处理一类多重背包物品
// wi：单件重量，vi：单件价值，si：可取上限，dp：一维背包数组，W：背包容量
void proc(int wi, int vi, int si, vector<ll>& dp, int W) {
    // 二进制拆分：把 si 拆成 1,2,4,... 份，转成若干 0-1 物品
    for (int k = 1; si > 0; k <<= 1) {
        int c = min(k, si);          // 本次取 c 件
        int wt  = wi * c;            // 合并后重量
        int val = vi * c;            // 合并后价值
        // 0-1 背包：从大到小遍历容量，保证每组只能选一次
        for (int j = W; j >= wt; j--) {
            dp[j] = max(dp[j], dp[j - wt] + val);
        }
        si -= c;                     // 减去已拆分的件数
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, W;
    cin >> N >> W;
    // 动态数组存储每类物品参数
    vector<int> w(N), v(N), s(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i] >> s[i];
    }

    // 一维 dp[j]：背包容量为 j 时的最大价值
    vector<ll> dp(W + 1, 0);

    // 对每一类物品进行二进制拆分，然后当作 0-1 背包处理
    for (int i = 0; i < N; i++) {
        proc(w[i], v[i], s[i], dp, W);
    }

    // 答案：容量恰为 W 时的最大价值
    cout << dp[W] << "\n";
    return 0;
}