Acwing 10. 有依赖的背包问题（01背包 依赖性

添加链接描述

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int h[N],e[N],ne[N],idx;
int n,m;
int v[N],w[N],dp[N][N];
//dp表示第i的son里选不超过j空间的最大值
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!=-1;i=ne[i])//遍历结点
    {
        int son=e[i];
        dfs(son);//子节点
        for(int j=m-v[u];j>=0;j--)//包含当前结点空间遍历01背包
        {
            for(int k=0;k<=j;k++)//枚举子树的空间
            {
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);
                //状态转移方程
            }
        }
    }
    for(int i=m;i>=v[u];i--)dp[u][i]=dp[u][i-v[u]]+w[u];//大于等于当前结点的空间的价值补上
    for(int i=0;i<v[u];i++)dp[u][i]=0;//空间不够为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);
        }
    }
    dfs(root);
    cout<<dp[root][m]<<endl;

    return 0;
}