问题 G: 运动鞋

时间限制: 1 Sec  内存限制: 128 MB

提交: 40  解决: 19

[][][]

题目描述

经过几个月的艰苦学习，Iserlohn终于赢得了全额奖学金。作为一个运动鞋狂热爱好者，他决定用所有的钱在运动鞋商店进行消费。 

有一些球鞋Iserlohn要收集，如Air Jordan 和 Nike Pro。而每个品牌已发布各种产品。由于，Iserlohn绝对是一个运动鞋狂热，他意欲购买每个品牌至少有一个产品。 

虽然每个产品的都有相应的定价，但是在Iserlohn心中也有一个价值倾向。由于他的钱有限，他希望最大限度地提高鞋的总价值。显然，作为一个收藏家，他不会购买相同产品的两次。 

现在，Iserlohn需要你帮他找到他的答案，即在至少购买每个品牌的一个产品的情况下，使得所有运动鞋在他心中的总价值最高。 

 

输入

第1行包含三个整数N，M，K（1<=N<=100，1 <= M<= 10000，1<=K<=10）分别表示共有N种产品，M的钱和K种品牌。 

接下来N行，每行三个整数a，b，c（1<=a<=k, 0<=b,c<100000）分别表示该商品属于哪种品牌，商品标价以及他心目中的价格。 

 

输出

只有一个正整数，输出他心中的最大价值，如果不能满足他的要求，输出“Impossible”

 

样例输入

5 10000 3 1 4 6 2 5 7 3 4 99 1 55 77 2 44 66

样例输出

255

这是一道背包DP的题目，但与一般背包不同的地方在于，有个要求限制，每一个牌子的鞋子至少买一双，这样就是转移时必须上一个牌子必须买过不为初始状态的一个值，才可以转移过来。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXM=10007;const int MAXN=107;const int MAXK=17;int n,m,k,dp[MAXK][MAXM],c[MAXK][MAXN],w[MAXK][MAXN],num[MAXK];void init();int main(){        int x,y,z;    while (~scanf("%d%d%d",&n,&m,&k))    {        init();        for (int i=1;i<=n;i++)        {            scanf("%d%d%d",&x,&y,&z);            num[x]++;            c[x][num[x]]=y;            w[x][num[x]]=z;        }        for (int i=1;i<=k;i++)        {            for (int j=1;j<=num[i];j++)                for (int k=m;k>=c[i][j];k--)                    {                        if (dp[i][k-c[i][j]]!=-1)                        {                            dp[i][k]=max(dp[i][k],dp[i][k-c[i][j]]+w[i][j]);                        }                        if (dp[i-1][k-c[i][j]]!=-1)                        {                            dp[i][k]=max(dp[i][k],dp[i-1][k-c[i][j]]+w[i][j]);                        }                    }        }        if (dp[k][m]!=-1) printf("%d\n",dp[k][m]);        else printf("Impossible\n");    }}void init(){    memset(dp,-1,sizeof(dp));    memset(dp[0],0,sizeof(dp[0]));    memset(c,0,sizeof(c));    memset(w,0,sizeof(w));    memset(num,0,sizeof(num));}