acwing10. 有依赖的背包问题

题目

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

题解

f[u][i]表示以u为父节点，体积为j的最大价值。

可以从父节点开始，先将父节点装入空间，然后再将剩余的体积按照分组背包分配给子树。

#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int e[N],ne[N],h[N],idx;
int n,m,p;
int v[N],w[N];
int f[N][N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    for(int i=h[u];~i;i=ne[i]){
        int son=e[i];
        dfs(e[i]);
        //先将u节点的位置空出来，再以u为父节点选择它的子树是否需要选择
        for(int j=m-v[u];j>=0;j--){
            for(int k=0;k<=j;k++){//选择父节点后只剩下j个空间，k需要从0到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];//由于前面已经将u的空间位置空出来，那么需要将u的价值加上
    for(int i=0;i<v[u];i++)f[u][i]=0;//如果装不下u了，那么u的所有子树也不能选了，即为0
}
int main(){
    cin>>n>>m;
    int root =1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>p;
        if(p==-1)root=i;
        else add(p,i);
    }
    dfs(root);
    cout<<f[root][m];
    
    return 0;
}