学步园

分组背包:每组最少选一个

Iserlohn 要买运动鞋，商店总共有n双运动鞋Iserlohn喜欢，

他总共有V元钱，这些运动鞋分为k类，

没类都有自己的编号id，单价p，对Iserlohn的价值v。

Iserlohn想每一类运动鞋至少买一双，在不超过他所拥有的总金额前提下，

使他得到的v最大。

易得状态转移方程：

    f[j][v]= max(f[j][v-cos]+val，f[j-1][v-cos]+val);

#include<stdio.h>
#include<string.h>
#define In -999999999
int max(int a,int b)
{
    if(a>b)return a;
    return b;
}
int dp[15][10010];
int main()
{
    int w[110],v[110],num[110];
    int i,j,k,n,V,m;
    while(scanf("%d%d%d",&n,&V,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&num[i],&v[i],&w[i]);        
        for(i=1;i<=m;i++)
            for(j=0;j<=V;j++)
                dp[i][j]=In;
        for(i=1;i<=m;i++)
        {
            for(k=1;k<=n;k++)
            {
                if(num[k]!=i)continue;
                for(j=V;j>=v[k];j--)
                {
                        dp[i][j]=max(dp[i][j],max(dp[i][j-v[k]]+w[k],dp[i-1][j-v[k]]+w[k]));
                }
                /*for(j=0;j<=V;j++)
                    printf("%d ",dp[i][j]);
                printf("\n");*/
            }
        }
        if(dp[m][V]>=0)
        printf("%d\n",dp[m][V]);
        else printf("Impossible\n");
    }
    return 0;
}