#include <bits/stdc++.h>
using namespace std;

// 多重背包1
int main() {
    scanf("%d %d", &N, &M);
    int x, y, z;
    for (int i = 1; i <= N; ++i) {
        scanf("%d %d %d", &x, &y, &z);
        while (z--) {
            for (int j = M; j >= x; --j) {
                dp[j] = max(dp[j], dp[j - x] + y);
            }
        }
    }
    printf("%d\n", dp[M]);
}

// 多重背包二进制优化
#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e6 + 10, maxM = 2e3 + 10;
int dp[maxM], v[maxN], m[maxN], N, M;

int main() {
    scanf("%d %d", &N, &M);
    int cnt = 0;
    for (int i = 1; i <= N; ++i) {
        int x, y, z, k = 1; scanf("%d %d %d", &x, &y, &z);
        while (k <= z) {
            m[++cnt] = x * k;
            v[cnt] = y * k;
            z -= k, k *= 2;
        }
        if (z > 0) {
            m[++cnt] = x * z;
            v[cnt] = y * z;
        }
    }

    // printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i) {
        for (int j = M; j >= m[i]; --j) {
            dp[j] = max(dp[j], dp[j - m[i]] + v[i]);
        }
    }
    printf("%d\n", dp[M]);
    return 0;
}

单调队列优化

 #include <bits/stdc++.h>
 using namespace std;

 const int maxN = 1e3 + 10, maxM = 2e4 + 10;
 int dp[2][maxM], v[maxN], w[maxN], c[maxN], N, M, q[maxM];

 int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) cin >> v[i] >> w[i] >> c[i];

    for (int i= 1; i <= N; ++i) {
        for (int r = 0; r < v[i]; ++r) {
            int hh = 1, tt = 0;
            for (int j = r; j <= M; j += v[i]) {
                while (hh <= tt && (j - q[hh]) > v[i] * c[i]) ++hh;
                while (hh <= tt && dp[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= dp[(i - 1) & 1][j]) --tt;
                q[++tt] = j;
                dp[i & 1][j] = dp[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << dp[N & 1][M] << endl;
    return 0;
 }