题解 | 【模板】分组背包

#include <iostream>
#include <cstring>


using namespace std;

const int N = 2010;
int w[N],v[N],h[N];

long long f[N][N];

int ne[N],idx;

void add(int c,int a,int b){
    w[idx] = a;
    v[idx] = b;
    ne[idx] = h[c];
    h[c] = idx++;
}

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

    memset(h, -1, sizeof h);
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(c,a,b);
        cnt = max(c,cnt);
    }

    for(int i = 1;i <= cnt;i++){
        for(int j = 0;j <= m;j++){
            f[i][j] = f[i - 1][j];
            for(int k = h[i];k != -1;k = ne[k]){
                if(j >= w[k]){
                    f[i][j] = max(f[i][j],f[i - 1][j - w[k]] + v[k]);
                }
            }
        }
    }
    cout<<f[cnt][m];
}
// 64 位输出请用 printf("%lld")