线性扩展到树
考虑前i个物品-> 考虑以u为根节点的子树
从前往后-> 从下往上

将每棵子树根据体积，看作有m + 1中选择方式的分组背包问题
这样就避免了枚举子树的所有不同种类的选法，例如当前子树除根节点外有k个节点，最坏情况下的时间复杂度为O(2k)
本质：树形DP + 分组背包

  • 整个框架是树形DP
  • 递归求每个子树是分组背包
  • 对于根节点来说，每个子树相当于一个分组（按体积）

理解：
单看两层树结构，包含根节点和一些叶节点，其中根节点是必选的。问题就变成了要么什么都不选，要么根节点必选剩余叶节点组成01背包问题
两层扩展至三层，对于中间一层来讲，已经求出每棵子树各个体积下对应的最大价值，而且是一一对应，此时对于根节点来讲，问题变成了要么什么都不选，要么根节点必选剩余子树组成分组背包问题，每个分组由不同体积对应的最大价值组成。

背包问题_8.pdf :::danger PDF的内容是第一次学习的笔记，已经很陈旧了，以下面的代码为准，更易懂一些! :::

AcWing 10. 有依赖的背包问题

题目描述
有 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

思路：
树形DP + 分组背包
时间复杂度：O(NV2)

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 110;
  5.     static int[][] f = new int[N][N];
  6.     static int[] h = new int[N], e = new int[N], ne = new int[N];
  7.     static int[] v = new int[N], w = new int[N];
  8.     static int n, m, idx;
  10.     static void add(int a, int b) {
  11.         e[idx] = b;
  12.         ne[idx] = h[a];
  13.         h[a] = idx++;
  14.     }
  16.     public static void main(String[] args) {
  17.         Scanner sc = new Scanner(System.in);
  18.         n = sc.nextInt();
  19.         m = sc.nextInt();
  21.         Arrays.fill(h, -1);
  22.         int root = 0;
  23.         for (int i = 1; i <= n; i++) {
  24.             v[i] = sc.nextInt();
  25.             w[i] = sc.nextInt();
  26.             int p = sc.nextInt();
  27.             if (p == -1) root = i;
  28.             else {
  29.                 add(p, i);
  30.             }
  31.         }
  33.         dfs(root);
  34.         System.out.println(f[root][m]);
  35.     }
  37.     static void dfs(int u) {
  39.         for (int j = v[u]; j <= m; j++) {
  40.             f[u][j] = w[u];
  41.         }
  43.         for (int i = h[u]; i != -1; i = ne[i]) {
  44.             int son = e[i];
  45.             dfs(son);
  47.             for (int j = m; j >= v[u]; j--) {    //注意这里是从大到小枚举
  48.                 for (int k = 0; k <= j - v[u]; k++) {
  49.                     f[u][j] = Math.max(f[u][j], f[u][j - k] + f[son][k]);
  50.                 }
  51.             }
  52.         }
  53.     }
  54. }