分组背包其实是01背包的思想，因为虽然有多组，但实际上每次也是考虑单个是选择还是不选择的问题，只是多了个组别而已，各组看成是独立的，根据题意建立状态转化方程。 http://acm.hdu.edu.cn/showproblem.php?pid=3033 设置一个动态数组dp【i】【j】表示此时j元买前i种鞋最大价值（给鞋编种类从1到K）；
//#include<bits/stdc++.h> #include<iostream> #include<cstring> #include<string> using namespace std; const int inf = 0x3f3f3f3f; int weight[15][150]; int val[15][150]; int dp[105][10005]; int max(int a,int b) { if(a>b)return a; else return b; } int main() { ios::sync_with_stdio(false); cin.tie(0); int N,M,K; while(cin>>N>>M>>K) { int a,b,c; int a1[11]; //int b1[11]; int bb[11]; memset(bb,0,sizeof(bb)); for(int i=0;i<N;i++) { cin>>a>>b>>c; weight[a][++bb[a]]=b; val[a][bb[a]]=c; } for(int i=0;i<=K;i++) for(int j=0;j<=M;j++) { if(i==0)dp[i][j]=0; else dp[i][j]=-inf;//给每一个初始化为最小负数 } //for(int i=1;i<=K;i++) //for(int j=1;j<=bb[i];j++) //cout<<"i="<<i<<"j="<<j<<endl; for(int i=1;i<=K;i++) for(int j=1;j<=bb[i];j++) for(int k=M;k>=weight[i][j];k--) { int v=k-weight[i][j]; dp[i][k]=max(dp[i][k],max(dp[i-1][v]+val[i][j],dp[i][v]+val[i][j]));//若dp[i][k]<0说明，dp[i-1][v]<0（注意：一开始初始时是最小的负数，则现在依然是很小的负数，可以看着加上任何范围内的正数后依然是负数）说明v元无法买前(i-1)种鞋，说明dp[i][v]<0说明v元也无法买前i种鞋，说明dp[i][k]<0，即转态转化后依然是k元无法买前i种鞋 } if(dp[K][M]<0)//小于0说明M元无法买K种鞋 cout<<"Impossible"<<endl; else cout<<dp[K][M]<<endl; } } 在这里插入代码片