转为01背包

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f, MOD = 1E9 + 7;
const int N = 1e3 * 20 + 10, M = 1e3 + 5;
int n, m, cnt, v[N], w[N], f[M];
int main(int argc, char* argv[]) {
    cin >> n >> m;
    for (int i = 1,a,b,c; i <= n; i++) {
        cin >> a >> b >> c;
        if (c == -1) c = m / a;
        int base = 1;
        while (c >= base) {
            v[++cnt] = a * base, w[cnt] = b * base;
            c -= base, base <<= 1;
        }
        if (c)
            v[++cnt] = a * c, w[cnt] = b * c;
    }

    for (int i = 1; i <= cnt; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}