拆成01背包

#include <iostream>
#include <algorithm>
using namespace std;

#define N 25000

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

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

    for (int i = 1; i <= n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int k = 1;
        while (k <= c)  // 直接拆成01背包
        {
            v[++cnt] = a * k;
            w[cnt] = b * k;
            c -= k;
            k <<= 1;
        }
        if (c > 0)
        {
            v[++cnt] = a * c;
            w[cnt] = b * c;
        }
    }

    for (int i = 1; i <= cnt; i++)   // 再来一遍01背包就 欧克了
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j] , f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}