请求添加题解

#include<bits/stdc++.h>
using namespace std;
struct BAG{
	int weight,value;
};
int dp[1005]={};
int n,m;
map<int,vector<BAG> > bag;
int main(){
	cin>>m>>n;
	for(int i=0,a,b,c;i<n;i++){
		cin>>a>>b>>c;
		bag[c].push_back({a,b});
	}
	for(map<int,vector<BAG> >::iterator i=bag.begin();i!=bag.end();i++){
		if((i->second).size()==0)continue;
		int cnt=(i->first);
		int tdp[1005]={};
		for(int j=0;j<bag[cnt].size();j++){
			for(int k=m;k>=bag[cnt][j].weight;k--){
				tdp[k]=max(tdp[k],dp[k-bag[cnt][j].weight]+bag[cnt][j].value);
			}
		}
		for(int k=m;k>=0;k--){
			dp[k]=max(tdp[k],dp[k]);
		}
	}
	cout<<dp[m];
	return 0;
}