这道题的意思是有K中品牌的鞋N个，每种品牌会有多个不同款式的鞋， 一个收藏家要收藏这些鞋，对于他来说这些鞋有一个估价，除此之外这些鞋也有标价， 且收藏家不会收藏多于一个的一种品牌同一款式的鞋， 且收藏家必须要至少收藏一种品牌的鞋一个，问收藏家拿着M块钱买回来鞋的估价最大是多少？？不存在的话就输出impossible..这个题乍一看是一个分组背包的题， 但是与传统的分组背包所不同的是这个题要求每组至少选一个物品，而传统的是每组中至多选一个，那我们先看看传统的多重背包的状态方程f[j] = max(f[j], f[j-w]+v),这样的方程由于max第一项的存在可能会导致有一组中一个物品都没选， 因此我们应该禁止这种状态的转移建立新的状态方程。。考虑每一组中的一个鞋， dp[i][j]表示在前i个品牌的鞋中收藏家用j块钱恰好能得到的最大估价， 那么 dp[i][j] = max(dp[i-1][j-w[k]]+v[k], dp[i][j-w[k]]+v[k])， 那么答案就是max(dp[K][j]) k = 0-M; 实现的时候应该注意初始状态应该设dp[0][0] = 0;其他为负无穷或者-1或者其他无意义的负数，表示该状态无效。递推的时候也应该注意， 具体细节看代码：
Wa点：1.递推式的推导 2.注意递推式的顺序 3：初始化
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int inf = 0x3f3f3f3f; int N, M, K; struct Wu { int b, c; Wu(){} Wu(int b, int c):b(b), c(c) {} }; vector<Wu> wu[15]; int f[12][100000 + 100]; //钱数为j时的最大价值 int main() { while(scanf("%d%d%d", &N, &M, &K) == 3) { for(int i=1; i<=K; i++) wu[i].clear(); for(int i=1; i<=N; i++) { int t, a, b; scanf("%d%d%d", &t, &a, &b); wu[t].push_back(Wu(a, b)); } /*for(int i=1; i<=K; i++) { printf("K = %d:", i); for(int j=0; j<wu[i].size(); j++) printf("%d %d", wu[i][j].b, wu[i][j].c); printf(" "); }*/ memset(f, -1, sizeof(f)); f[0][0] = 0; //for(int i=0; i<=K; i++) f[i][0] = 0; for(int i=1; i<=K; i++) for(int k=0; k<wu[i].size(); k++) //考虑第i组的第K个物品 { //printf("wu[%d].size = %d ", i, wu[i].size()); for(int j=M; j>=wu[i][k].b; j--) { if(f[i][j-wu[i][k].b] >= 0) //这个必须放到前面 否则会出错。。discuss里面有坑爹数据 f[i][j] = max(f[i][j], f[i][j-wu[i][k].b]+wu[i][k].c); if(f[i-1][j-wu[i][k].b] >= 0) f[i][j] = max(f[i][j], f[i-1][j-wu[i][k].b]+wu[i][k].c); } /* for(int tp=0; tp<=M; tp++) printf("%d ", f[i][tp]); printf(" ");*/ } bool flog = false; int res = 0; for(int i=M; i>=0; i--) if(f[K][i] >= 0) { flog = true; res = max(res, f[K][i]); } if(!flog) printf("Impossible "); else printf("%d ", res); } return 0; }