Consumer

  
  

   
   3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60
  
  

  
  

   
   210
  
  
  
  


  
  

题意：有很多个箱子，想买箱子中的物品必须先买下箱子，求在规定的钱数里最多能买多大价值的东西

思路：第一道依赖背包的题目，这一题是比较简单的依赖背包。。。首先要买这个箱子里的物品，肯定要买下箱子，这题比较简单，箱子自身没有价值，只有价格。并且箱子里的物品是独立的，不是箱子里的物品是箱子，还可以有东西，就是不是箱子里可以套箱子。。否则就是树形DP，这种就是背包九讲里的一种做法，对每个箱子进行01背包，得到费用依次为0..V-c[i]所有这些值时相应的最大价值f'[0..V-c[i]]，因为有n组物品，然后就等于对这n组再做一次01背包，求在容量v中，哪种箱子最合适。最后一定要每个容量都要比较下选这个箱子跟不选哪个最优，当前箱子不一定是必选的，具体看代码

下面这句话引自背包九讲里的依赖背包：http://www.jb51.cc/article/p-ewaissfn-bqn.html

“再考虑P06中的一句话：可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c[i]所有这些值时相应的最大价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费用为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次背包后，将主件转化为V-c[i]+1个物品的物品组，就可以直接应用的算法解决问题了。”

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 5;
int dp[55][maxn];
int main()
{
    int n,tw,bag_v,bag_w,v,w;
    while(~scanf("%d%d",&n,&tw))
    {
        memset(dp,sizeof(dp));
        for(int i = 1; i <= n; i++)  //一共n组
        {
            scanf("%d%d",&bag_v,&bag_w);   //其实下面的操作都是假设已经买了第i个箱子，所以直接下面直接扣去箱子的价格
            for(int j = 0; j < bag_v; j++) dp[i][j] = -1;  //这里是防止买不起箱子，其实下面可以加一个if就行
            for(int j = bag_v; j <= tw; j++) dp[i][j] = dp[i-1][j-bag_v] + 0;  //因为箱子只有价格没有价值，对当前箱子操作的时候，都要减去“入场券”，即如果想买这个箱子里面的东西，必须要减去箱子的价格，因为箱子没有价值，所以v = 0， 就+0，因为总体是对n个箱子做01背包，所以是dp[i-1][j-v],其实这里就是分组背包里v-0,下面那个循环就是每个“主件”里的每个物品
            for(int k = 1; k <= bag_w; k++)  //箱子买完了，里面的东西随意买了，这里的每个dp[][j]的j都是已经减去箱子的价格了
            {
                scanf("%d%d",&w,&v);
                for(int j = tw; j >= w; j--)  //就是对第i层（第i个箱子）做01背包
                {
                    if(dp[i][j-w] != -1)  //防止连箱子都买不起
                        dp[i][j] = max(dp[i][j],dp[i][j-w]+v);  //第i个箱子做01
                }
            }
            for(int j = 0; j <= tw; j++)
                dp[i][j] = max(dp[i][j],dp[i-1][j]);  //前面是假设第i个箱子一定买了，其实他还可以不买这个箱子最优。。在这里抉择对所有容量"v"买不买这个箱子最优，这里就拉倒n个箱子的层面了
        }
        printf("%d\n",dp[n][tw]);
    }
    return 0;
}