HDU 3449 Consumer 詳細(xì)題解（依賴背包）

2019-11-08 01:45:24

字體：大中小

供稿：網(wǎng)友

Consumer

Time Limit: 4000/2000 MS (java/Others) Memory Limit: 32768/65536 K (Java/Others)Total Submission(s): 2125 Accepted Submission(s): 1143PRoblem DescriptionFJ 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. InputThe 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) OutputFor each test case, output the maximum value FJ can get Sample Input

3 800300 2 30 50 25 80600 1 50 130400 3 40 70 30 40 35 60 Sample Output210
題意：有很多個(gè)箱子，想買箱子中的物品必須先買下箱子，求在規(guī)定的錢數(shù)里最多能買多大價(jià)值的東西
思路：第一道依賴背包的題目，這一題是比較簡單的依賴背包。。。首先要買這個(gè)箱子里的物品，肯定要買下箱子，這題比較簡單，箱子自身沒有價(jià)值，只有價(jià)格。并且箱子里的物品是獨(dú)立的，不是箱子里的物品是箱子，還可以有東西，就是不是箱子里可以套箱子。。否則就是樹形DP，這種就是背包九講里的一種做法，對每個(gè)箱子進(jìn)行01背包，得到費(fèi)用依次為0..V-c[i]所有這些值時(shí)相應(yīng)的最大價(jià)值f'[0..V-c[i]]，因?yàn)橛衝組物品，然后就等于對這n組再做一次01背包，求在容量v中，哪種箱子最合適。最后一定要每個(gè)容量都要比較下選這個(gè)箱子跟不選哪個(gè)最優(yōu)，當(dāng)前箱子不一定是必選的，具體看代碼
下面這句話引自背包九講里的依賴背包：http://blog.csdn.net/QQ_34374664/article/details/56015253
“再考慮P06中的一句話： 可以對每組中的物品應(yīng)用P02中“一個(gè)簡單有效的優(yōu)化”。 這提示我們，對于一個(gè)物品組中的物品，所有費(fèi)用相同的物品只留一個(gè)價(jià)值最大的，不影響結(jié)果。所以，我們可以對主件i的“附件集合”先進(jìn)行一次01背包，得到費(fèi)用依次為0..V-c[i]所有這些值時(shí)相應(yīng)的最大價(jià)值f'[0..V-c[i]]。那么這個(gè)主件及它的附件集合相當(dāng)于V-c[i]+1個(gè)物品的物品組，其中費(fèi)用為c[i]+k的物品的價(jià)值為f'[k]+w[i]。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉(zhuǎn)化為V-c[i]+1個(gè)物品的物品組，就可以直接應(yīng)用P06的算法解決問題了。”
#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, 0, sizeof(dp));        for(int i = 1; i <= n; i++)  //一共n組        {            scanf("%d%d", &bag_v, &bag_w);   //其實(shí)下面的操作都是假設(shè)已經(jīng)買了第i個(gè)箱子，所以直接下面直接扣去箱子的價(jià)格            for(int j = 0; j < bag_v; j++) dp[i][j] = -1;  //這里是防止買不起箱子，其實(shí)下面可以加一個(gè)if就行            for(int j = bag_v; j <= tw; j++) dp[i][j] = dp[i-1][j-bag_v] + 0;  //因?yàn)橄渥又挥袃r(jià)格沒有價(jià)值，對當(dāng)前箱子操作的時(shí)候，都要減去“入場券”，即如果想買這個(gè)箱子里面的東西，必須要減去箱子的價(jià)格，因?yàn)橄渥記]有價(jià)值，所以v = 0， 就+0，因?yàn)榭傮w是對n個(gè)箱子做01背包，所以是dp[i-1][j-v],其實(shí)這里就是分組背包里v-0,下面那個(gè)循環(huán)就是每個(gè)“主件”里的每個(gè)物品            for(int k = 1; k <= bag_w; k++)  //箱子買完了，里面的東西隨意買了，這里的每個(gè)dp[][j]的j都是已經(jīng)減去箱子的價(jià)格了            {                scanf("%d%d", &w, &v);                for(int j = tw; j >= w; j--)  //就是對第i層（第i個(gè)箱子）做01背包                {                    if(dp[i][j-w] != -1)  //防止連箱子都買不起                        dp[i][j] = max(dp[i][j], dp[i][j-w]+v);  //第i個(gè)箱子做01                }            }            for(int j = 0; j <= tw; j++)                dp[i][j] = max(dp[i][j], dp[i-1][j]);  //前面是假設(shè)第i個(gè)箱子一定買了，其實(shí)他還可以不買這個(gè)箱子最優(yōu)。。在這里抉擇對所有容量"v"買不買這個(gè)箱子最優(yōu)，這里就拉倒n個(gè)箱子的層面了        }        printf("%d/n", dp[n][tw]);    }    return 0;}其實(shí)這個(gè)題可以用滾動數(shù)組的。。。因?yàn)閕是從1-n的，每個(gè)i都比較了要不要當(dāng)前箱子，所以i-1就是前i-1最好的情況了，每次只與前面那個(gè)狀態(tài)有關(guān)。。但是這個(gè)題數(shù)據(jù)不大，二維數(shù)組就行。。