实在是懒得在外面用markdown再写一遍,直接使用注释得了。。。

简单注释便于理解，记录学习！

参考代码：

#include <iostream>

using namespace std;

const int N = 20000;

int n, m, v[N], w[N], f[N];

// 将s[i]件分为logs[i]组，从0~s[i]中选等同于从logs[i]组中进行01选择，选与不选完全可以拼凑成s[i]种情况
// s[i]种该物品，相当于logs[i]组每组分别为2^(0~logs[i])件物品，本意为从n种物品中选择若干件，优化后变成了从n * logs[i]种物品中选择0件或一件，转化为了0 1 背包问题。
// 优化本质似乎就是空间换时间吧！

// 原暴力复杂度：O(n * m * s)
// 优化后复杂度：O(n * logs * m)

int main(){
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        int a, b, s;
        cin >> a >> b >>s;
        int k = 1;
        // 对每组物品进行拆分
        // 保证k的变化在剩余s的范围内
        while(k <= s){
            cnt ++;
            v[cnt] = a * k, w[cnt] = b * k;
            s -= k, k <<= 1;
        }
        // 当前的k * 2 >= 剩余的s 则凑一个常数进行匹配，使得可以使用（选与不选）凑到0 ~ s[i]的范围
        if(s > 0){
            cnt ++;
            v[cnt] = a * s, w[cnt] = b * s;
        }
    }

    // 更新新的物品数
    n = cnt;

    // 一维优化01背包求解
    for(int i = 1; i <= n; i++)
        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;
}