HDU OJ 3303 I love sneakers!【动态规划之分组背包入门】

题意：看样例：
5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66

第一行中 5 代表有5个物品，（以下有5行，即每个物品信息），10000代表现在的钱数（即背包体积），3代表物品分3个品牌，以下有5行，每行第一个数
为品牌，第二个为花费钱数（即占用体积），第三个为获得的价值。
满足一下条件：1：每个物品最多能拿一次（即01背包） 2：每个品牌的物品至少拿一个！！
求满足条件的最大价值！！若无输出
Impossible 。
思路：这个分组背包和我们常见的分组背包（每组最多拿1个）有很大区别。但是代码只需要
把3层循环的顺序改变一下，初始化改变一下即可。。具体的自己比较代码、、
AC代码：
[cpp]
/*分组背包*/
#include<stdio.h>
#include<string.h>
int dp[20][10050];
struct hi
{
    int x;
    int y;
}w[20][200];
int max(int a,int b)
{
    if(a<b) a=b;
    return a;
}
int main()
{
    int a,b,c,n,m,v;
    while(~scanf("%d%d%d",&n,&v,&m))
    {
        int g[20]={0};
        for(a=0;a<n;a++)
        {
            scanf("%d",&b);
            scanf("%d%d",&w[b][g[b]].x,&w[b][g[b]].y);
            g[b]++;    www.zzzyk.com
        }
        /*for(a=1;a<=m;a++)
        {    for(b=0;b<g[a];b++)
            {
                printf("-->%d %d",w[a][b].x,w[a][b].y);
            }
            printf("\n");}*/
        memset(dp,-9999,sizeof(dp));
        dp[0][0]=0;
        for(a=1;a<=m;a++)
        {
            for(b=0;b<g[a];b++)
            {
                for(c=v;c>=w[a][b].x;c--)
                {
                    dp[a][c]=max(dp[a][c],max(dp[a-1][c-w[a][b].x]+w[a][b].y,dp[a][c-w[a][b].x]+w[a][b].y));
                }
            }
        }
        int ans=0;
        for(a=0;a<=v;a++)
            if(ans<dp[m][a])
                ans=dp[m][a];
        if(ans!=0)
            printf("%d\n",ans);
        else
            puts("Impossible");
    }
}

作者：PIAOYI0208

补充：软件开发 , C++ ,