HDU3449 Consumer（有依賴背包）

【題目連結】

http://acm.hdu.edu.cn/showproblem.php?pid=3449

題目意思

有N個箱子，每個箱子需要花費Ai的代價

箱子裡面有K個物品，K個物品你可以選擇買任意個，但每個物品隻能買一個，每個物品有相應的花費和價值

你又M的大洋，最後問最多能得到多少價值物品。

解題思路

先對每組選擇裡的所有物品進行0-1背包處理，但背包容量為（總容量-盒子容量）；然後跟上一組的狀态比較來決定這一組選擇 是選還是不選，取其中的較大值。

代碼部分

#include<stdio.h>
#include<string.h>
const int MAX=;
int dp[MAX];
int tmp[MAX];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,sum,p,m,w,v,i,j,k;
    while(scanf("%d%d",&n,&sum)!=EOF)
    {
        memset(dp,,sizeof(dp));
        for(i=;i<n;i++)
        {
            scanf("%d%d",&p,&m);
            memcpy(tmp,dp,sizeof(dp));//繼承前面的
            for(j=;j<m;j++)
            {
                scanf("%d%d",&w,&v);
                for(k=sum-p;k>=w;k--)//先将附件進行1次01背包
                    tmp[k]=max(tmp[k],tmp[k-w]+v);
            }
            for(j=p;j<=sum;j++)//更新能更新的
                dp[j]=max(dp[j],tmp[j-p]);    //分組背包
        }
        printf("%d\n",dp[sum]);
    }
    return ;
}