今天是我们讲解「动态规划专题」中的「背包问题」的第十六篇。
今天将学习「树形背包」问题。
另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。
你可以先尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 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」与「分组背包」问题的结合。
首先我们先将常规的「分组背包」状态定义从”线性“调整为”树形“。
然后发现如果采取常规的分组背包的「枚举方案」做法,最多会有
个方案需要被枚举,复杂度过高。
再利用最终的
必然是由各种具有实际使用容量的方案中取最大值而来,利用”已有维度”对原本的
中方案进行划分,从而将复杂度从
优化到
。
最终得到复杂度为
的树形背包问题解决方案。