题解 | 【模板】分组背包

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

const int N=2e3+10;

int n,m;
int dp[N];


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	
	int a,b,c,max_num=0;
	vector<int> v[N],w[N];
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c;
		w[c].push_back(a);
		v[c].push_back(b);
		max_num=max(max_num,c);
	}
	
	for(int i=1;i<=max_num;i++){
		for(int j=m;j>=0;j--){
			for(int k=0;k<v[i].size();k++){
				if(w[i][k]<=j) dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
			}
		}
	}
	cout<<dp[m]<<endl;
    return 0;
}