洛谷P1757 通天之分组背包

 1 //分组背包 
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int n,m,k,tot,f[1005];//tot-组数 
 5 vector< pair<int,int> >d[105];
 6 int main()
 7 {
 8     scanf("%d%d",&m,&n);
 9     for(int i=1,x,y,z;i<=n;++i) scanf("%d%d%d",&x,&y,&z),d[z].push_back(make_pair(x,y)),tot=max(tot,z);
10     for(int k=1;k<=tot;++k)
11         for(int j=m;j>=0;--j)//注意三层循环顺序 
12             for(int i=0;i<d[k].size();++i)
13                 if(j>=d[k][i].first) f[j]=max(f[j],f[j-d[k][i].first]+d[k][i].second);
14     printf("%d",f[m]);
15     return 0;
16 }