背包问题之有依赖的背包

package com.zhang.reflection.面试.算法模版.背包问题模版;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
 * 有 N 个物品和一个容量是 V 的背包。
 * 物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
 * 如果选择物品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
 */

public class 有依赖的背包问题 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();//物品的个数
        int C = sc.nextInt();//背包容量
        int[] V = new int[N];//物品的体积
        int[] W = new int[N];//物品的价值
        int[] P = new int[N];//所依赖物品的编号
        for (int i = 0; i < N; i++) {
            V[i] = sc.nextInt();//第i个物品的体积
            W[i] = sc.nextInt();//第i个物品的价值
            P[i] = sc.nextInt();//第i个物品所依赖的物品编号
        }
        int ans = dependPack(N, C, V, W, P);
        System.out.println(ans);
    }

    private static int dependPack(int N, int C, int[] V, int[] W, int[] P) {
        // dp[i][j]：选择以 i 为子树的物品，在容量不超过 j 时所获得的最大价值
        int[][] dp = new int[N][C + 1];

        // 建立一个数组，每个下标存放对应 “以该下标为父节点” 的所有子节点（root 节点的编号为 1）
        // 该数组下标为 0 的存放的是 root 节点，下标为 1 存放的是以 root 节点为父节点的结点 ...
        List<Integer>[] tree = new List[N + 1];
        Arrays.setAll(tree, e -> new ArrayList<Integer>());
        int root = -1;
        for (int i = 0; i < N; i++) {
            if (P[i] == -1) {
                root = i;
            } else {
                tree[P[i]].add(i);
            }
        }

        // dfs 求解
        dfs(N, C, V, W, dp, root, tree);
        // 最终答案是以 root 为子树（代表了 root 本身也是可以被选或不选）、容量不超过 C 的最大价值
        return dp[root][C];
    }
    private static void dfs(int N, int C, int[] V, int[] W, int[][] dp, int root, List<Integer>[] tree) {
        int vi = V[root];
        int wi = W[root];
        for (int i = vi; i <= C; i++) {
            dp[root][i] = wi;
        }
        List<Integer> child = tree[root + 1]; // root 的编号为 1
        int size = child.size();
        for (int i = 0; i < size; i++) {
            int node = child.get(i);
            dfs(N, C, V, W, dp, node, tree);
            for (int j = C; j >= vi; j--) {
                for (int k = 0; k <= j - vi; k++) {
                    dp[root][j] = Math.max(dp[root][j], dp[root][j - k] + dp[node][k]);
                }
            }
        }
    }
}