最普通代码：

#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;
}