本文主要是介绍Consumer HDU - 3449 （有依赖的背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Consumer
题目链接：HDU - 3449
题意：FJ要去购物，买的商品要用箱子装起来，每个箱子装不同的商品，问FJ能获得的最大价值；
只有先买了箱子，才能买固定的物品，所以这是个有依赖的背包问题，对于每个箱子内的物品一定是按01背包看是否要买；
对于每个箱子有两个状态，买，不买；买了就必定买了对应商品，那么买了这一箱子后，用剩下的钱买商品；
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int dp[maxn], temp[maxn];
int main(){int n, w;while(~scanf("%d%d", &n, &w)){//printf("n: %d w: %d\n", n, w);memset(dp, 0, sizeof(dp));for(int i=1; i<=n; i++){memcpy(temp, dp, sizeof(dp));int p, m;scanf("%d%d", &p, &m);//printf("p: %d m: %d\n", p, m);for(int k=1; k<=m; k++){int c, v;scanf("%d%d", &c, &v);//printf("c:%d v:%d\n", c, v);for(int j=w-p; j>=c; j--){temp[j]=max(temp[j], temp[j-c]+v);}}for(int j=p; j<=w; j++){dp[j]=max(dp[j], temp[j-p]);}}printf("%d\n", dp[w]);}return 0;
}
这篇关于Consumer HDU - 3449 （有依赖的背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
