python/TangDou/BeiBao/bbdc2.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 12010;
int n, m;
int v[N], w[N];
int f[N];
int idx;
//多重背包的二进制优化
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int vi, wi, si;
        cin >> vi >> wi >> si;//二进制优化,能打包则打包之，1,2,4,8,16,...
        int b = 1;
        while (b <= si) {
            v[++idx] = vi * b;
            w[idx] = wi * b;
            si -= b;
            b *= 2;
        }
        //剩下的
        if (si > 0) {
            v[++idx] = vi * si;
            w[idx] = wi * si;
        }
    }
    for (int i = 1; i <= idx; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf("%d", f[m]);
    return 0;
}