题目描述

给N个物品和V容量的背包，求出最大价值。
这些物品存在依赖关系也就是买1的话就要买2这样的。
像是树一样。

思路

因为是树所以理所当然的使用深搜，但纯粹深搜效率太低这又是背包则两个结合起来使用。
使用一个二维数组d[x][v]，表示的状态分别是以x为根不超过v容量的最大价值。
因为是有根且有解的所以可以直接从根开始搜，但根节点是必须拿的。
所以深搜到的点我们都直接遍历然后递归下去接着直接开始计算。
并且状态不是M开始而是M-v[x]这样才能算出来它的最大价值。
而这样的话从M-v[x]就得到零来结束了因为必须全部都计算到。
而在计算完毕之后一定要把小于v[x]的重量的d数组内全部改为零因为之后或许会加上它

代码

#include<cstdio>

using namespace std;

const int sz=101;
int n,m,i,x,rt,ct,v[sz],nt[sz],h[sz],a[sz],b[sz],d[sz][sz];

void add(int x,int y){v[++ct]=y,nt[ct]=h[x],h[x]=ct;}

int max(int a,int b){return a>b?a:b;}

void ss(int x)
{
    int i,j,k,y;

    for(i=h[x];y=v[i],i;i=nt[i])
    {
        ss(y);
        for(j=m-a[x];~j;--j)for(k=0;k<=j;++k)d[x][j]=max(d[x][j],d[x][j-k]+d[y][k]);
    }

    for(i=m;i>=a[x];--i)d[x][i]=d[x][i-a[x]]+b[x];
    for(i=0;i<a[x];++i)d[x][i]=0;

}

int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d%d",a+i,b+i,&x);
        if(x==-1)rt=i;
        else add(x,i);
    }

    ss(rt);

    printf("%d",d[rt][m]);

    return 0;
}