题目描述

有 N 个物品和一个容量是 V 的背包。

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

输入格式
第一行有两个整数 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

算法1

多叉树转二叉树

时间复杂度

参考文献

C++ 代码

#include <iostream>

using namespace std;

const  int C = 105;
int n, m;

int v[C], w[C];
int l[C], r[C]; //分别存储左孩子和右孩子,如果是多叉树，采用左孩子，右兄弟的方法存储
int bigson[C];

int f[C][C];

int dfs(int i, int j) {
    if (f[i][j] || i == 0 || j == 0) return f[i][j];
    f[i][j] = dfs(r[i], j);
    for (int k = 0; k <= j - v[i];  k ++)
        f[i][j]  = max(f[i][j], dfs(l[i], j-v[i] - k)+ dfs(r[i], k) + w[i]);
     return f[i][j];
}



int main() {
    cin >> n >> m;
    int root = 0;
    for (int i = 1; i <= n; i ++) {
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else {
            if (bigson[p] == 0) l[p] = i;
            else r[bigson[p]] = i;
            bigson[p] = i;

        }
    }
    cout << dfs(root, m) << endl;
    return 0;
}

算法2

需要先学会dfs序
dfs序后倒着做0,1背包，f[i][j]可以理解为从i往后剩余j的容量产生的最大值

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int C = 105;

int h[C], ne[C], e[C], idx;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int N, V;
int v[C], w[C];
int f[C][C];
int size[2 * C], dfsx[2 * C];
int new_v[C], new_w[C];
int cnt;


void dfs(int x) {
    dfsx[x] = ++cnt;
    size[cnt] = 1;
    new_v[cnt] = v[x];
    new_w[cnt] = w[x];
    for(int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j);
        size[dfsx[x]] += size[dfsx[j]];
    }
}


int main() {
    cin >> N >> V;
    int root;
    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);

    for(int i = N; i >= 1; i --)
    {
        for(int j = 0; j <= V;j ++)
        { 
            f[i][j] = f[i+size[i]][j];
            if(j >= new_v[i])
                f[i][j] = max(f[i][j],f[i+1][j-new_v[i]] + new_w[i]);

        }
    }

    cout << f[1][V];
    return 0;
}

算法3

采用分组背包的思想，直接对多叉树进行分组背包, 可以将j倒序循环，这样缩小一维空间，和yxc代码差不多。
golang代码如下，虽然不是c++，但其实很好懂
f[i][j][k]表示以i为根的子树，前j个孩子，用k体积产生的最大价值
转移就是第j个孩子选与不选, sonj表示第j个孩子
选的话就是 f[i][j-1][k-分配给sonj的体积] + f[sonj][sonj的孩子总数][分配给sonj的体积]
不选的话就是 f[i][j-1][k]

package main

import (
    "bufio"
    "fmt"
    "os"
)

var (
    n, v, root       int
    vi, wi           []int
    fatherIdx2sonIdx map[int][]int
    f  [][][]int
)

func main() {
    reader := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
    fmt.Fscan(reader, &n, &v)
    fatherIdx2sonIdx = make(map[int][]int)
    vi = make([]int, n+1)
    wi = make([]int, n+1)
    f = make([][][]int, n+1)
    for i := 1; i <= n; i++ {
        f[i] = make([][]int, n+1)
        var pi int
        fmt.Fscan(reader, &vi[i], &wi[i], &pi)
        if pi == -1 {
            root = i
        } else {
            fatherIdx2sonIdx[pi] = append(fatherIdx2sonIdx[pi], i)
        }

    }
    dfs(root)
    fmt.Fprintln(w, f[root][len(fatherIdx2sonIdx[root])][v])
}

func dfs(u int) {
    f[u][0] = make([]int, v+1)
    for j := vi[u]; j <= v; j++ {
        f[u][0][j] = wi[u]
    }
    for key, sonIdx := range fatherIdx2sonIdx[u] {
        i := key+1
        dfs(sonIdx)
        sonSize := len(fatherIdx2sonIdx[sonIdx])
        f[u][i] = make([]int, v+1)
        for j := vi[u]; j <= v; j++ {
            for k := 0; k <= j - vi[u]; k++ {
                f[u][i][j] = max(f[u][i][j], f[u][i-1][j-k]+f[sonIdx][sonSize][k])
            }
        }
    }
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}