题目描述
有依赖的背包问题是指物品之间存在依赖关系,这种依赖关系可以用一棵树来表示,要是我们想要选择子节点就必须连同其父节点一块选。
我们可以把有依赖的背包问题看成是分组背包问题,每一个结点是看成是分组背包问题中的一个组,子节点的每一种选择我们都看作是组内的一种物品,因此我们可以通过分组背包的思想去写。
但它的难点在于如何去遍历子节点的每一种选择,即组内的物品,我们的做法是从叶子结点开始往根节点做,并使用数组表示的邻接表来存贮每个结点的父子关系。
样例
算法1
(闫神代码)
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int n,m;
int h[N],e[N],ne[N],idx;
/*h数组是邻接表的头它的下表是当前节点的标号,值是当前结点第一条边的编号(其实是最后加入的那一条边),e数组是边的集合,它的下标是当前边的编号,数值是当前边的终点;
ne是nextedge,如果ne是-1表示当前结点没有下一条边,ne的下标是当前边的编号,数值是当前结点的下一条边的编号,idx用于保存每一条边的上一条边的编号。
这样我们就知道了当前结点的第一条边是几,这个边的终点是那个结点,该节点的下一条边编号是几,那么邻接表就完成了
*/
int v[N],w[N],f[N][N];
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;//该方法同于向有向图中加入一条边,这条边的起点是a,终点是b,加入的这条边编号为idx
}
void dfs(int u){
for(int i = h[u];i!=-1;i = ne[i]){//对当前结点的边进行遍历
int son = e[i];//e数组的值是当前边的终点,即儿子结点
dfs(son);
for(int j = m-v[u];j>=0;j--){
//遍历背包的容积,因为我们是要遍历其子节点,所以当前节点我们是默认选择的。
//这个时候当前结点我们看成是分组背包中的一个组,子节点的每一种选择我们都看作是组内一种物品,所以是从大到小遍历。
//我们每一次都默认选择当前结点,因为到最后根节点是必选的。
for(int k = 0;k<=j;k++){//去遍历子节点的组合
f[u][j] = max(f[u][j],f[u][j-k]+f[son][k]);
}
}
}
//加上刚刚默认选择的父节点价值
for(int i = m;i>=v[u];i--){
f[u][i] = f[u][i-v[u]]+w[u];
}
//因为我们是从叶子结点开始往上做,所以如果背包容积不如当前物品的体积大,那就不能选择当前结点及其子节点,因此赋值为零
for(int i = 0;i<v[u];i++){
f[u][i] = 0;
}
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
int root;
for(int i = 1;i<=n;i++){
int p;
cin>>v[i]>>w[i]>>p;
if(p==-1){
root = i;
}else{
add(p,i);//如果不是根节点就加入邻接表,其中p是该节点的父节点,i是当前是第几个节点
}
}
dfs(root);
cout<<f[root][m]<<endl;
return 0;
}
很细节,ORZ,受教了
蒟蒻求问,for(int j = m-v[u];j>=0;j–) 这一句的 m-v[u] 为啥改成 m 也能AC?
刚刚想到一点,是不是下面加上父节点值的那个循环直接给覆盖了?
大于m-v[u]的部分相当于算了但没用
牛皮!
如果背包容积不如当前物品的体积大的时候,为啥要特意置0啊,本来不就是0吗
因为在三层for里面有给赋值,所以需要在循环后置零
可以可以
很详细,感谢!
屮 我是先会写的树状 再去写的分组
有些不理解体积为啥从大到小枚举
可以想一下01背包,依赖背包其实就是01背包的变形
打错了吧兄弟,你应该不理解的是从大到小吧。
可是 01 背包在未进行滚动数组空间优化时不是可以体积从小到大循环的吗?这里好像必须要体积从大到小循环才能过。
我觉得是因为
对u的某个子节点son,算f[u][j]的时候用到了f[u][j - k],这时的f[u][j - k]需要是没有用son的结果更新过的(因为只能用一次son),所以循环要从大到小
(我也琢磨了半天为什么,感觉明白了一点又讲不太清楚
可以的!!!
很详细,看完y总的分组背包想一下就明白了,感谢
很详细,点赞!
感谢大佬!!