HDU 3449 Consumer （依赖背包）

Consumer

Time Limit: 4000/2000 MS (Java/Others)   

Memory Limit: 32768/65536 K (Java/Others)

Total Submission(s): 778    Accepted Submission(s): 419

Problem Description FJ is going to do some shopping, and before that, he needs some boxes to carry the different kinds of stuff he is going to buy. Each box is assigned to carry some specific kinds of stuff (that is to say, if he is going to buy one of these stuff, he has to buy the box beforehand). Each kind of stuff has its own value. Now FJ only has an amount of W dollars for shopping, he intends to get the highest value with the money.  

Input

The first line will contain two integers, n (the number of boxes 1 <= n <= 50), w (the amount of money FJ has, 1 <= w <= 100000) Then n lines follow. Each line contains the following number pi (the price of the ith box 1<=pi<=1000), mi (1<=mi<=10 the number goods ith box can carry), and mi pairs of numbers, the price cj (1<=cj<=100), the value vj(1<=vj<=1000000)  

Output

For each test case, output the maximum value FJ can get  

Sample Input

3 800

300 2 30 50 25 80

600 1 50 130

400 3 40 70 30 40 35 60  

Sample Output

210

思路：每个箱子以及它能装的物品构成一个分组，若当前组为第 i 组，考虑要取该组中的物品，则要在前 i-1 组在最大费用为 w - p的情况下的最优值去更新。（其中w为最大费用，p为第 i 组中箱子的费用，因为要取第 i 组，所以必须预留p费用给该组的箱子用）参照《背包九讲》可以知道，对于有依赖的背包，可以先对附件进行01背包(在已经预留了p费用的情况下)，所以对于每一个组，先将之前的最优值继承下来，然后根据自己组的附件进行01背包，既dp[i] = max(dp[i], dp[i - cost] + val)。其中dp[i]表示费用为 i 时的最优值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define SIZE 100005

using namespace std;

int dp[SIZE];
int dp2[SIZE];
int n,w;

int main()
{
    while(~scanf("%d%d",&n,&w))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            int p,m;
            scanf("%d%d",&p,&m);
            memcpy(dp2,dp,sizeof(dp));
            for(int j=1; j<=m; j++)
            {
                int temp1,temp2;
                scanf("%d%d",&temp1,&temp2);
                for(int k=w-p; k>=temp1; k--)
                    dp2[k] = max(dp2[k],dp2[k-temp1]+temp2);
            }
            for(int k=p; k<=w; k++)
                dp[k] = max(dp[k],dp2[k-p]);
        }
        printf("%d\n",dp[w]);
    }
    return 0;
}