Just 代码 + 注释

/* 
    数据较大必须优化，朴素版的多重背包会TLE
    这里采用将每种物品的最大个数用二进制拆分 --> 将 s 优化为 logs
    <因为任何一个数都可以由二进制拼凑而来，而此处按逐个二进制拆分打包（2^0, 2^1, ..., 2^k）
                直至无法拆为下一个2的整次幂（2^(k+1)）就将剩余个数全部打包为最后一个部分>
    【故问题转化为对每次打包过后的新物品<即将每一次打包的一坨原物品整体看作一个新物品>
                    （体积转化为打包个数*单个体积，价值转化为打包个数*单个价值）的01背包问题】
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000; // 打包后的新物品最大个数 --> N * logs

int n, m;
int v[N], w[N]; // 分别存放打包后的新物品的体积和价值
int f[N]; // 优化后的一维01背包写法

int main() {
    cin >> n >> m;

    int cnt = 0; // 打包次数（等同于打包后的新物品的个数）
    for (int i = 1; i <= n; ++ i) { 
        int a, b, s;
        scanf("%d%d%d", &a, &b, &s);

        int k = 1; // 打包物品个数，2^(k - 1)
        while (k <= s) { // 当打包个数<=剩下的物品个数(k <= s)时，继续按二进制划分打包
            cnt ++ ; // 打包次数+1
            v[cnt] = k * a; // 将此次打包后的新物品体积(k * a)存放(v[cnt])
            w[cnt] = k * b; // 将此次打包后的新物品价值(k * b)存放(w[cnt]) 
            s -= k; // 将s更新为打包后的剩下物品个数
            k *= 2; // 将k更新为下一次要打包的物品个数
        }
        if (s) { // 如果还有剩下的物品个数（即无法完美的按照二进制打包而剩下的物品个数）
            cnt ++ ; // 则再次打包，将剩下的所有物品一起打包
            v[cnt] = s * a; // 存放此次打包的新物品体积
            w[cnt] = s * b; // 存放此次打包的新物品价值
        }
    }

    n = cnt; // 将n更新为打包次数（即转化[打包]后的新物品个数）
    for (int i = 1; i <= n; ++ i)  // 用一维的01背包计算
        for (int j = m; j >= v[i]; -- j)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl; // 输出答案

    return 0; // 结束快乐~
}