题目描述

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

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

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

输出最大价值。

输入要求

第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。

如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。

样例

输入

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出

11

C++ 代码

//树形DP
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110;
int n,m;
int v[N],w[N];
int h[N],ne[N],e[N],idx;
int 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;i=ne[i])   //物品组  遍历u号点的所有子树
    {
        int son=e[i];     //当前的终点，为儿子节点     子结点编号
        dfs(e[i]);        //递归节点转移
        //分组背包
        //f[root][j] 表示以root为根节点的子树，并且体积小于j的最大价值  
        for(int j=m-v[u];j>=0;j--)
        //体积  //因为u是该树的根节点（根据题意可得）,所以必选,预留出u的空间
          for(int k=0;k<=j;k++) 
          //决策
             f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);//状态方程
    }
    注意下面的几行都为枚举的物体的体积
    //因为这个u在刚才的分组背包中没有加入，所有要将物品u这个点加到f当中
    for(int i=m;i>=v[u];i--)   f[u][i]=f[u][i-v[u]]+w[u];
    //体积小于当前节点的体积，为不合法，所有置0，
    for(int i=0;i<v[u];i++)  f[u][i]=0;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);//初始化邻接表
    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<<f[root][m]<<endl;
    return 0;
}