【动态规划/背包问题】树形背包问题

前言

今天是我们讲解「动态规划专题」中的「背包问题」的第十六篇。

今天将学习「树形背包」问题。

另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。

你可以先尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~

题目描述

有

个物品和一个容量为

的背包，物品编号为

。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。

如下图所示：

如果选择一个物品，则必须选择它的父节点。

第

件物品的体积为

，价值为

，其父节点物品编号为

，其中根节点

。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

提示：

树形背包

树形背包又称为 树上背包 或是 有依赖的背包问题 。

其是「树形 DP」与「分组背包」的结合。

我们可以先回顾一下 分组背包。

在常规的「分组背包」问题中，我们采用的状态定义为：

为考虑前

个物品组，背包容量不超过

的最大价值。

从状态定义我们发现，常规的分组背包问题对物品组的考虑是“线性“的（从前往后考虑每个物品组）。

然后在状态转移时，由于物品组之间没有依赖关系，限制只发生在”组内“（每组「最多」选择一件物品）。

所以常规分组背包问题只需要采取「枚举物品组 - 枚举背包容量 - 枚举组内物品（决策）」 的方式进行求解即可。

而在树形背包问题中，每个物品的决策与其父节点存在依赖关系，因此我们将”线性“的状态定义调整为”树形“的：

为考虑以

为根的子树，背包容量不超过

的最大价值。

首先，根据树形背包的题目限制，对于以

为根的子树，无论选择哪个节点，都需要先把父节点选上。

在此前提下，我们不失一般性的考虑

该如何转移：

如果从选择节点

的哪些子树入手的话，我们发现节点

最坏情况下会有

个子节点，而每个子节点都有选和不选两种决策，因此总的方案数为

，这显然是不可枚举的。

这时候可以从”已有维度“的层面上对方案进行划分，而不是单纯的处理每一个具体方案。

我们知道最终这

个方案的最大价值会用于更新

。

我们可以根据「容量」这个维度对这

个方案进行划分：

• 消耗容量为

的方案数的最大价值；

• 消耗容量为

的方案数的最大价值； ...

• 消耗容量为

的方案数的最大价值；

消耗的容量的范围为

，是因为需要预留

的容量选择当前的根节点

。

综上，最终的状态转移方程为（

为节点

的子节点）：

从状态转移方式发现，在计算

时需要用到

，因此我们需要先递归处理节点

的子节点

的状态值。

代码：

class Solution {
    int N = 110, M = N * 2;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    int[] vi, wi;
    int n, c, idx;
    // 定义 f[u][j] 为考虑以 u 为根的子树，背包容量不超过 j 的最大价值
    int[][] f = new int[N][N];

    // 链式向前星存图
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        idx++;
    }

    void dfs(int u) {
        // 节点 u 的价值和体积
        int cw = wi[u], cv = vi[u];
        // 要选任一节点，必须先选 u，同时也限制了至少需要 cv 的容量
        for (int i = cv; i <= c; i++) f[u][i] += cw;

        // 遍历节点 u 的所有子节点 x（分组背包遍历物品组）
        for (int i = he[u]; i != -1; i = ne[i]) {
            int x = e[i];
            // 递归处理节点 x
            dfs(x); 
            // 从大到小遍历背包容量（分组背包遍历容量）
            for (int j = c; j >= 0; j--) {
                // 遍历给节点 x 分配多少背包容量（分组背包遍历决策）
                for (int k = 0; k <= j - cv; k++) {
                    f[u][j] = Math.max(f[u][j], f[u][j - k] + f[x][k]);        
                }
            }
        }
    }

    public int maxValue(int N, int C, int[] p, int[] v, int[] w) {
        n = N; c = C;
        vi = v; wi = w;
        Arrays.fill(he, -1);
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (p[i] == -1) {
                root = i;
            } else {
                add(p[i], i);
            }
        }
        dfs(root);
        return f[root][c];
    }
}

• 时间复杂度：建图的复杂度为

；共有

个状态需要被计算，每个状态的计算需要遍历分配多少容量给子节点，复杂度为

。整体复杂度为

• 空间复杂度：

总结

今天我们学习了「树形背包」问题，其就是「树形 DP」与「分组背包」问题的结合。

首先我们先将常规的「分组背包」状态定义从”线性“调整为”树形“。

然后发现如果采取常规的分组背包的「枚举方案」做法，最多会有

个方案需要被枚举，复杂度过高。

再利用最终的

必然是由各种具有实际使用容量的方案中取最大值而来，利用”已有维度”对原本的

中方案进行划分，从而将复杂度从

优化到

。

最终得到复杂度为

的树形背包问题解决方案。

背包问题（目录）

1. 01背包 : 背包问题 第一讲
   1. 【练习】01背包 : 背包问题 第二讲
   2. 【学习&练习】01背包 : 背包问题 第三讲
2. 完全背包 : 背包问题 第四讲
   1. 【练习】完全背包 : 背包问题 第五讲
   2. 【练习】完全背包 : 背包问题 第六讲
   3. 【练习】完全背包 : 背包问题 第七讲
3. 多重背包 : 背包问题 第八讲
4. 多重背包（优化篇）
   1. 【上】多重背包（优化篇）: 背包问题 第九讲
   2. 【下】多重背包（优化篇）: 背包问题 第十讲
5. 混合背包 : 背包问题 第十一讲
6. 分组背包 : 背包问题 第十二讲
   1. 【练习】分组背包 : 背包问题 第十三讲
7. 多维背包
   1. 【练习】多维背包 : 背包问题 第十四讲
   2. 【练习】多维背包 : 背包问题 第十五讲
8. 树形背包 : 本篇
   1. 【练习篇】树形背包
9. 背包求方案数
   1. 【练习】背包求方案数
10. 背包求具体方案
    1. 【练习】背包求具体方案
11. 泛化背包
    1. 【练习】泛化背包