I love sneakers! 分组背包DP
/*一道分组背包的题。比赛的时候循环顺序整反了。悲剧了。f[i][j]=max(max(f[i][j],f[i-1][j-c[i][p]]+w[i][p]),f[i][j-c[i][p]]+w[i][p]);表示取到前i个牌子时取到的最大的价值。而每个牌子必须至少取一次。每个物品最多取一次。f[i][j]，f[i][j-c[i][p]]+w[i][p]保证在同一牌子内取或不取。f[i-1][j-c[i][p]]+w[i][p])在不同的牌子内取或不去。如果最后的状态都无法更新仍为-1.则不满足条件。#include <stdio.h>#include <vector>#include <iostream>#define maxn 10001int f[11][maxn];int max(int a,int b){ return a>b?a:b;}using namespace std;int main(){ int n,m,k,t,a,b; vector<int> c[maxn]; vector<int> w[maxn]; while(scanf("%d%d%d",&n,&m,&k)==3) { for(int i=1; i<=n; i++) { scanf("%d%d%d",&t,&a,&b); c[t].push_back(a); w[t].push_back(b); } for(int i=1; i<=k; i++) for(int j=0; j<=maxn; j++) f[i][j]=-1; for(int i=1; i<=k; i++) for(int p=0; p<c[i].size();p++) for(int j=m; j>=0; j--) if(j>=c[i][p]) { f[i][j]=max(max(f[i][j],f[i-1][j-c[i][p]]+w[i][p]),f[i][j-c[i][p]]+w[i][p]); } if(f[k][m]==-1) printf("Impossible\n"); else printf("%d\n",f[k][m]); for(int i=0;i<maxn;i++) { c[i].clear(); w[i].clear(); } } return 0;}