有依赖的背包

原题链接

关键：当递归处理u结点的子树返回时，进行分组背包的决策，各个子树中的结点可能非常多，可能有100多个结点，因此，如果以方案来划分最多有2^100种类别，所以要改用体积来划分

从j表示当前除去v[u]的体积，j从[ m - v [u] , 0 ]的体积中枚举（类别）,k选取体积是0，是1......是j（选一个）——>转化为分组背包问题

转移方程为：dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k])

物品组选完以后，再将u结点如，此时需要枚举背包剩余体积
1.对于j>=v[u]&&j<=m的体积，可以装入u结点，更新相应的dp数组
2.对于j<v[u]的体积，无法装入u结点，因此以u为根节点的子树不存在，dp[u][j]=0;

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=110;

int n,m;
int h[N],e[N],idx,ne[N];
int v[N],w[N];
int dp[N][N];//表示在所有以u为根的子树中选，且总体积不超过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;i=ne[i])//枚举物品组
    {
        int son=e[i];
        dfs(e[i]);
        
        //分组背包的过程,对于这一组子树内部以体积划分
        for(int j=m-v[u];j>=0;j--)//循环体积,先给v[u]腾出位置来
            for(int k=0;k<=j;k++)//循环决策,枚举当前用多少体积
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);//不要写成w[i],是子树的体积和质量
    }
    
    //在体积为j时,再将当前u加进去
    //相应更新dp数组
    for(int j=m;j>=v[u];j--)dp[u][j]=dp[u][j-v[u]]+w[u];
    for(int j=0;j<v[u];j++) dp[u][j]=0;
}


int main()
{
    int root;
    
    cin>>n>>m;
    
    memset(h,-1,sizeof h);
    
    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;
}