分组背包问题，大意**要买鞋，有k种牌子，每种牌子至少买一双鞋子。每双鞋子有标价跟实际价值。求用m多的钱买最多价值的鞋。

其实我觉得这题的难点就在处理“至少”这点上面。

状态方程很多都能推出用 dp[k][m] 来表示 已经买了k种鞋 在有m钱状态下的 鞋的最大价值。

状态转移方程为

for( k = 1 ; k <= K ; k++)
        {
            for( i = 0 ; i < num[k] ; i++)
            {
                for( j = mm ; j >= m[k][i].m ; j--)
                {
                    if(dp[k][j - m[k][i].m] != -1)
                        dp[k][j] = Max(dp[k][j] , dp[k][j - m[k][i].m] + m[k][i].v);
                    if(dp[k-1][j - m[k][i].m] != -1 )
                        dp[k][j] = Max(dp[k][j] , dp[k-1][j - m[k][i].m] + m[k][i].v);

}
            }
        }

如果忽略了两个红色的判断句，大家都看得出这只是单纯的01背包且 没有条件限制，加了这两句就能实现至少了。理由如下

一开始我将dp[][]数组初始化为-1表示所有的数都不合法。大于0表示合法

然后将所有的 k = 0 dp[0][]置为0，这是为了 k = 1时能合法计算。

从状态方程中看出，当上一个状态值为-1时表示他不合法。所以当前状态没有计算的必要也不合法答案。

如果计算完第k类商品的取值后，所有的dp[k][]均为-1的时候，第k类表明没有一鞋被买。故所有状态都不合法，接下来的所有值也都将不合法。

在计算第k组商品的过程中，当某个-1变成一个非负数的时候，也就表明当前的第k种已经拿了第i件物品，所以变成合法答案了。

如此推下去，最后一个值dp[k][m],就是答案了。如果依然是-1，就输出impossible把。

5 13 3
1 2 3
1 4 6
2 10 2
3 2 2
3 1 2

7

m   k=0   k=1   k=2   k=3 
0    0    -1    -1    -1 
1    0    -1    -1    -1
2    0    3    -1    -1
3    0    3    -1    -1
4    0    6    -1    -1
5    0    6    -1    -1
6    0    9    -1    -1
7    0    9    -1    -1
8    0    9    -1    -1
9    0    9    -1    -1
10   0    9    -1    -1
11   0    9    -1    -1
12   0    9    5     -1
13   0    9    5      7

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

struct node{

   int w;

   int v;

}que[][];

int num[];

int dp[][];

int main(){

   int n,m,kk;

   while(scanf("%d%d%d",&n,&m,&kk)!=EOF){

        memset(num,,sizeof(num));

        memset(dp,-,sizeof(dp));

      for(int i=;i<=n;i++){

            int x,y,z;

          scanf("%d%d%d",&x,&y,&z);

          que[x][num[x]].w=y;

          que[x][num[x]].v=z;

          num[x]++;

      }

      for(int i=;i<=m;i++)

        dp[][i]=;

      for(int i=;i<=kk;i++){

        for(int k=;k<num[i];k++){

            for(int j=m;j>=que[i][k].w;j--){

                if(dp[i][j-que[i][k].w]!=-)

                    dp[i][j]=max(dp[i][j],dp[i][j-que[i][k].w]+que[i][k].v);

                  if(dp[i-][j-que[i][k].w]!=-)

                    dp[i][j]=max(dp[i][j],dp[i-][j-que[i][k].w]+que[i][k].v);

            }

        }

      }

      if(dp[kk][m]<)

        printf("Impossible\n");

      else

        printf("%d\n",dp[kk][m]);

   }

   return ;

}