題目鏈接：http://acm.split.hdu.edu.cn/showproblem.php?pid=3449

?

Consumer

?

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

?

大意：在購買一類物品之前，必須買另一種物品。

本題是購買袋子，有體積，但是沒有價值。

AC代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll long long const int maxn=1e5+5; const int INF=0x3f3f3f3f;int dp[maxn]; int temp[maxn];int main() {int N,P;while(scanf("%d%d",&N,&P)==2){memset(dp,0,sizeof(dp));for(int i=1; i<=N; i++){int p,m;scanf("%d%d",&p,&m);memset(temp,-1,sizeof(temp));for(int k=p; k<=P; k++)temp[k]=dp[k-p];while(m--){int a,b;scanf("%d%d",&a,&b);for(int k=P; k>=a; k--)if(temp[k-a]!=-1)temp[k]=max(temp[k],temp[k-a]+b);}for(int k=1; k<=P; k++)dp[k]=max(dp[k],temp[k]);}printf("%d\n",dp[P]);}return 0; }

一個寫的好幾種方法的博客：http://www.cnblogs.com/wuyiqi/archive/2011/11/26/2264283.html

轉載于:https://www.cnblogs.com/a-clown/p/6040268.html

總結

以上是生活随笔為你收集整理的hdu 3449 有依赖性的01背包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。