这道题的意思是有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 
     
      #include 
      
       #include 
       
        #include 
        
         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[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][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("\n");*/ } 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\n"); else printf("%d\n", res); } return 0;}