P156

写法一：O(N·V·logS)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int M = 2010; 
int n, m;
int f[M];

struct Good {
    int v, w;
};

int main () {
    vector<Good> goods; //因为不知道能拆分成多少组，所以用vector来表示物品（拆分后）
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2) { //把s拆成logs份
            goods.push_back({v * k, w * k});
            s -= k;
        }

        if (s > 0) {
            goods.push_back({v * s, w * s});
        }
    }

    for (auto good : goods) // 相当于01背包中枚举所有n个物品
        for (int j = m; j >= good.v; j --)
            f[j] = max(f[j], f[j - good.v] + good.w);
    cout << f[m] << endl;
    return 0;
}
*****************************************************************************************************
写法二：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;
int n, m;
int v[N], w[N], s[N];
int f[M];


int main () {
    cin >> n >> m;
    int cnt = 0;//定义在for循环，最终记录有多少新的组（01背包大组个数）

    for (int i = 1; i <= n; i ++) {
        int a, b, s;
        int k = 1; // 定义在for循环里面，记录原来每种物品的拆分情况 k=1 2 4 8 16 64 ....
        cin >> a >> b >> s;
        while (k <= s) {
            cnt ++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }

        if (s > 0) {
            cnt ++;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }    
    n = cnt;
    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;
}