1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int N=205;
 6 struct knapsack{
 7     int w,c,p;
 8 };
 9 knapsack ns[N];
10 int a[15][N],b[15][N],f[15][N];
11 int main(){
12     int m,n,t;
13     cin>>m>>n>>t;
14     for(int i=1;i<=n;i++)
15         cin>>ns[i].w>>ns[i].c>>ns[i].p;
16     //为每一组确定一个最优选择方案(一维数组)
17     for(int i=1;i<=m;i++){//column
18         for(int j=1;j<=n;j++){//row
19             if(i>=ns[j].w&&(ns[j].c>a[ns[j].p][i]||(ns[j].c==a[ns[j].p][i]&&ns[j].w<b[ns[j].p][i]))){
20                 a[ns[j].p][i]=ns[j].c;
21                 b[ns[j].p][i]=ns[j].w;
22             }
23         }
24     }
25     //联立所有组得到一个dp结果矩阵(二维数组) 
26     for(int i=1;i<=t;i++){
27         for(int j=1;j<=m;j++){
28             for(int k=0;k<=j;k++){
29                 f[i][j]=max(f[i][j],a[i][k]+f[i-1][j-b[i][k]]);
30             }
31         }
32     }
33     cout<<f[t][m]; 
34     return 0;
35 }

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 int w[31],c[31];
 6 int a[11][32],f[201];
 7 int main(){
 8     int m,n,t;
 9     cin>>m>>n>>t;
10     for(int i=1;i<=n;i++){
11         int p;
12         cin>>w[i]>>c[i]>>p;
13         a[p][++a[p][0]]=i;//a[p][i]代表p组中第i个物品在输入的哪一行
14     }
15     for(int k=1;k<=t;k++)//group
16         for(int j=m;j>=0;j--)//weight
17             for(int i=1;i<=a[k][0];i++)//组中的每一项
18                 if(j>=w[a[k][i]])
19                     f[j]=max(f[j],f[j-w[a[k][i]]]+c[a[k][i]]);
20     cout<<f[m];
21     return 0;
22 }