重学背包 | Yuhang's Blog

背包的数学记法。

0/1背包

给定正整数 $n$ 、 $V_{1}, V_{2}, \dots V_{n}$ 、 $W_{1}, W_{2}, \dots W_{n}$ 。对于任意自然数 $m$ ，定义集合族 $S (m)$ 为 $S (m) := {M ∣ \sum_{i \in M} V_{i} = m}$ 则0/1背包问题是对给定的 $m$ ，求 $f (m) := max_{M \in S (m)} \sum_{i \in M} W_{i}$ 递推求解。记 $S_{k} (m)$ 和 $f_{k} (m)$ 是上述两个定义对前 $k$ 个 $V_{i}$ 和 $W_{i}$ 考虑后得到的结果。现在考虑从 $k - 1$ 的情形递推到 $k$ 的情形，即将 $V_{k}$ 和 $W_{k}$ 新加入考虑。考虑 $S_{k} (m)$ 是如何构成的：

那些没有选择 $k$ 的集合，就是 $S_{k - 1} (m)$ 。即

${M ∣ M \in S_{k} (m) and k \notin M} = S_{k - 1} (m)$

那些选择了 $k$ 的集合，就是 $S_{k - 1} (m - V_{k}) \cup {k}$ 。即

${M ∣ M \in S_{k} (m) and k \in M} = S_{k - 1} (m - V_{k}) \cup {k}$ 由此可见， $S_{k - 1} (m)$ 和 $S_{k - 1} (m - V_{k}) \cup k$ 是 $S_{k} (m)$ 的一个划分。从而， $f_{k} (m) = max (max_{M \in S_{k - 1} (m)} \sum_{i \in M} W_{i}, max_{M \in S_{k - 1} (m - V_{k}) \cup k} \sum_{i \in M} W_{i}) f_{k} (m) = max (f_{k - 1} (m), f_{k - 1} (m - V_{k}) + W_{k})$ 初始值满足， $S_{0} (0) = \emptyset$ ，从而 $f_{0} (0) = 0$ 其他值应当设为负无穷。考虑实现。由于在 $k$ 的维度上， $f_{k} (m)$ 只依赖 $f_{k - 1} (m^{'})$ （其中 $m^{'} \leq m$ ），因此采取一维数组倒序循环即可。

完全背包

将0/1背包中的集合族 $S (m)$ 改为多重集合族即为完全背包。其结果为 $f_{k} (m) = max (f_{k - 1} (m), f_{k} (m - V_{k}) + W_{k})$ 实现中将倒序循环改为正序循环即可。

树上背包

给定一棵有根数，每个点有点权 $W_{i}$ ，选择一个点必须先选择它的父亲。一共选择 $m$ 个节点，要求最大化点权和。设 $f (u, m)$ 是以 $u$ 为根的子树选择 $m$ 个节点时最大的点权和。选择的依赖关系，等价于以 $u$ 为根的子树选择 $1$ 个节点时必须选择 $u$ ，即 $f (u, 1) = W_{u}$ 。下面逐个考虑 $u$ 的儿子 $v$ 。注意此时 $v$ 可以看作是背包中选择的物体，但这个物体的体积和价值均可随着其贡献的节点数变化。在利用 $v$ 更新 $u$ 的答案的时候，除了倒序遍历 $m$ ，还需要遍历 $v$ 的所有可能的体积和价值，即枚举 $v$ 的所有可能的贡献的节点数。