树上背包
这是最普遍的情况, 从树中选取 \(m\) 个结点, 最大化它们的价值之和.
符合直觉地, 设 \(f_{u, i}\) 表示从以 \(u\) 为根的子树中选取了 \(i\) 个结点的最大价值之和. 转移是显然的:
这样转移时间复杂度即为 \(\Theta(nm)\).
这是最普遍的情况, 从树中选取 \(m\) 个结点, 最大化它们的价值之和.
符合直觉地, 设 \(f_{u, i}\) 表示从以 \(u\) 为根的子树中选取了 \(i\) 个结点的最大价值之和. 转移是显然的:
这样转移时间复杂度即为 \(\Theta(nm)\).
有 \(n\) 个物品, 第 \(i\) 个重量为 \(a_{i}\), 求重量不大于 \(c\) 的情况下能够装下的最大重量.
\(n, m = \max\{a_{i}\} \leqslant 2 \times 10^{4}, c \leqslant 10^{9}.\)
假设有 \(p_{1}\leqslant p_{2}\leqslant p_{3}\leqslant p_{4}.\)
假设一个问题满足四边形不等式，那么它的决策点有单调性。
Proof:
根据最优决策的定义写出这个位置的转移式 :
两不等式相加，得到 :