题目描述

有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如下图所示:

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。
每件物品的编号是 i ，体积是v[i],价值是w[i],依赖的父节点编号是p[i]。物品的下标范围是1…N
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。
接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数v[i],w[i],p[i],用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 p[i]=−1,表示根节点。 数据保证所有物品构成一棵树。

输出格式

输出一个整数，表示最大价值。

输入样例

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

输出样例

11

(动态规划)

参考文献

算法基础课

C++代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int v[120],w[120];
int h[120],ne[120],e[120],idx;//idx是用来记录第几条边
int f[120][120];//状态表示:f[i][j]选取第i个点体积为j的情况下的最大价值
//属性：max
int n,m;
void add(int a,int b)//下面是来建立邻接表
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//e是记录几条边在数组里的编号，ne是用来记录下一条边，如果是-1表示没有下一条边(h开始初始化-1)
//h是用来记录所依赖的点是第几条边
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--)
          for(int k=0;k<=j;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];
    for(int i=0;i<v[u];i++)//如果连体积连v[u]都不能满足，就赋值为0
        f[u][i]=0;
}
int main()
{
    memset(h,-1,sizeof h);//初始化
    scanf("%d%d",&n,&m);
    int root;//根节点
    for(int i=1;i<=n;i++)
    {
        int c;
        scanf("%d%d%d",&v[i],&w[i],&c);
        if(c==-1) root=i;
        else add(c,i);
    }
    dfs(root);
    printf("%d",f[root][m]);//输出结果
    return 0;
}