本文主要是介绍第七重关：有依赖背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
已知如下条件：
N个物品
容量为V的背包
vi：第i个物品所占用的容量空间
valuei：第i个物品所获得的价值数值
但是包和包之间有依赖关系，例如，如果要是想选择A那么必须要先选择B（这里指考虑一重依赖关系，并且不会形成依赖环）
求解：
该背包可以装下的最大价值是多少？
解题思路：
开始的思路还是一样的枚举每一件物品，对于物品 i ，枚举其所有的依赖它的包，然后对这些包进行01背包处理，之后，在对物品 i 进行01背包的处理，此处需要注意的是，要使用到dp数组的一个拷贝。
for (int i = 1; i <= N; i++)
{memcpy(tmpdp, dp, sizeof(tmpdp));for (int k: son of i){for (int j = V; j >= v[k]; j--){tmpdp[j] = MAX(tmpdp[j], tmpdp[j - v[k]] + w[k]);}}for (int j = V; j >= v[i]; j--) // 在依赖 i 的包被处理过的情况下，再去处理 i 包{dp[j] = MAX(dp[j], tmpdp[j - v[i]] + w[i]);}
} 题目：HDU 3449（题意言简意赅）
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int max_n = 51;
const int max_w = 100001;
struct NODE
{int price, value;
};int MAX(const int x, const int y)
{if (x > y) return x;else return y;
}int main()
{int n, w;while (cin>> n>> w){vector<NODE>vec[max_n];int box_p[max_n];int dp[max_w], tmpdp[max_w];memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++){struct NODE node;int num;cin>> box_p[i]>> num;while (num--){cin>> node.price>> node.value;vec[i].push_back(node);}}for (int i = 1; i <= n; i++){memcpy(tmpdp, dp, sizeof(dp));for (int k = 0; k < vec[i].size(); k++){for (int j = w; j >= vec[i][k].price; j--){tmpdp[j] = MAX(tmpdp[j], tmpdp[j - vec[i][k].price] + vec[i][k].value);}}for (int j = w; j >= box_p[i]; j--){dp[j] = MAX(dp[j], tmpdp[j - box_p[i]]);}}cout<< dp[w]<< endl;}return 0;
}
这篇关于第七重关：有依赖背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
