背包的数学记法。
0/1背包
给定正整数$n$、$V_1, V_2, \dots V_n$、$W_1, W_2, \dots W_n$。对于任意自然数$m$，定义集合族$S(m)$为 $$ S(m) :=\{M \mid \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 \mid M \in S_k(m) \text{ and } k \not \in M \} = S_{k-1}(m) $$
- 那些选择了$k$的集合，就是$S_{k-1}(m-V_k) \cup \{k\}$。即
$$ \{ M \mid M \in S_k(m) \text{ 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) = \varnothing$，从而 $$ f_0(0) = 0 $$ 其他值应当设为负无穷。 考虑实现。由于在$k$的维度上，$f_k(m)$只依赖$f_{k-1}(m’)$（其中$m’ \le 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$的所有可能的贡献的节点数。