背包问题之有依赖的背包（包含模板）

有依赖的背包最好理解的题就是NOIP的金明的预算方案，其每个物品有主件和附件，附件必须在主件已经购买了的请款下才能购买，这里牵扯到有依赖的背包的一个问题，将这些进行分组之后就有多种情况即：不能购买主件，只能购买主件，能购买主件和多个附件，这些情况组成了多个可能的情况，
所以这种情况可以先将一个组当中的附件进行一次01背包得到其背包容量为0~V-w[i]时的所有可能情况，然后将整个组当成一个分组背包的一组看待，即此时的组里只需要选择一个可能性即可

我总结了下打出了一个模板，能简单包含这种题型，尤其时像金明的预算方案这样的题稍加修改就能通过：
模板奉上：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace
std;
//简易模板适用于被依赖的物品不能再成为别的物品的附件
struct node
{
long long w, v;
}a[1005];
int
d[1005];
vector<node>group[1005];
int n, m;
long long dp[1005];
void DP(vector<node>d)
{
if (d.size() > 1)//有附件
{
int k = m - d[0].w;//除了主件剩下的q空间
long long
*st;
st = new long long[k];
memset(st, 0, sizeof st);
for (int i = 1; i < d.size(); i++)//将附件进行组合,组合成多种可能
{
for (int j = k; j >= d[i].w; j++)
st[j] = max(st[j], st[j - d[i].w] + d[i].v);
}
for (int i = m; i >= 0; i--)//剩下的钱,作为分组背包计算
{
if (i >= d[0].w)//能买主件
{
for (int j = 0; j <= k; j++)
{
if (i >= d[0].w + j)
dp[i] = max(dp[i], dp[i - d[0].w - j] + d[0].v + st[j]);
}
}
}
}
else
{
for (int i = m; i >= d[0].w; i--)
dp[i] = max(dp[i], dp[i - d[0].w] + d[0].v);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i].w >> a[i].v >> d[i];
if (d[i] == 0)//主件
group[i].push_back(a[i]);
}
for (int i = 1; i <= n; i++)
if (d[i] != 0)//附件
group[d[i]].push_back(a[i]);//进行分组
for (int i = 1; i <= 1000; i++)
{
if (group[i].size() != 0)//是一个组
{
DP(group[i]);//每个大组进行一次有依赖的背包
}
}
cout << dp[m] << endl;
system("pause");
return 0;
}

后续会更新一种已经作为被依赖主件又是别的主件的附件的情况，还有树状DP的模板，神犇轻喷，写的不是很好，请耐心多看两遍。

最后

以上就是开朗曲奇为你收集整理的背包问题之有依赖的背包（包含模板）的全部内容，希望文章能够帮你解决背包问题之有依赖的背包（包含模板）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。