介绍背包九讲中的 0-1背包，完全背包，多重背包问题。
0-1 背包
$n$ 个物品，第 $i$ 个物品体积为 $v_i$， 价值为 $w_i$ 。给你一个容量为 $C$ 的背包，求装入背包的物品总价值最大是多少？
解答
令 $dp[i][j]$ 表示拿第 $i$ 个物品，体积为 $j$ 时的最大值
$dp[i][j] = \max(dp[i-1][j-v[i]]+w[i],dp[i-1][j])$
由于每个 $dp[i][\cdot]$ 只与 $dp[i-1][\cdot]$ 有关，故直接用一维数组保存即可
复杂度 $\mathcal{O} (n^2)$
1for(int i = 1; i <= n; i++) {
2 for(int j = C; j >= v[i]; j--) {
3 dp[j] = max(dp[j-v[i]]+w[i], dp[j]);
4 }
5}
完全背包
$n$ 种物品，每种物品无穷个，第 $i$ 种物品体积为 $v_i$， 价值为 $w_i$ 。给你一个容量为 $C$ 的背包，求装入背包的物品总价值最大是多少？
解答
令 $dp[i][j]$ 表示拿第 $i$ 种物品，体积为 $j$ 时的最大值
$dp[i][j] = \max(dp[i-1][j-k\cdot v[i]]+k\cdot w[i])$ 其中 $k$ 为第 $i$ 种物品拿的个数
由于每个 $dp[i][\cdot]$ 只与 $dp[i-1][\cdot]$ 有关，故直接用一维数组保存即可
复杂度 $\mathcal{O} (n^2)$
1for(int i = 1; i <= n; i++) {
2 for(int j = v[i]; j <= C; j++) {
3 dp[j] = max(dp[j-v[i]]+w[i], dp[j]);
4 }
5}
多重背包
$n$ 种物品，第 $i$ 种物品个数为 $s_i$，体积为 $v_i$， 价值为 $w_i$ 。给你一个容量为 $C$ 的背包，求装入背包的物品总价值最大是多少？
解答
令 $dp[i][j]$ 表示拿第 $i$ 种物品，体积为 $j$ 时的最大值
$dp[i][j] = \max(dp[i-1][j-k\cdot v[i]]+k\cdot w[i]),\ (0\leq k\leq s_i)$ 其中 $k$ 为第 $i$ 种物品拿的个数
由于每个 $dp[i][\cdot]$ 只与 $dp[i-1][\cdot]$ 有关，故直接用一维数组保存即可
将其转化为 0-1 背包 直接算复杂度为 $\mathcal O(n\sum_{i=1}^{n} s_i)$，下面介绍几种优化
二进制优化
可以将 $s_i$ 件物品拆分成 $1,2,4,8,\cdots,2^{k-1},s_i-2^{k}+1$ 件物品的组合。例如价值为 $3$，体积为 $4$，数量为 $10$ 的物品，可以拆成 $1+2+4+3$ 转化为价值为 $(3,6,12,8)$，体积为 $(4,8,16,12)$ 数量均为 $1$ 的 $4$ 件物品。每个 $s_i$ 都能转化成 $\lceil \log_2(s_i+1) \rceil$ 件物品，再利用 0-1 背包 求解即可。
**为何这样转换之后答案仍然对呢？**这是因为 $\forall x\in[0,s_i]$，总可以由 $s_i$ 件物品转化成的 $\lceil \log_2(s_i+1) \rceil$ 件物品的某个组合得到。以上例说明：$10$ 拆成 $1+2+4+3$。那么有 $$ 0=0, 1=1, 2=2, 3=3, 4=4, 5=1+4 , 6=2+4 \\ 7=1+2+4,8=1+4+3,9=2+4+3,10=1+2+3+4 $$
复杂度 $\mathcal O(n^2\log_2 n)$
1for(int i = 1; i <= n; i++) { //第 i 个物品
2 for(int k = 1; s[i]; s[i] -= k, k = min(k<<1, s[i])) { //二进制优化
3 for(int j = C; j >= k*v[i]; j--) {
4 dp[j] = max(dp[j-k*v[i]] + k*w[i], dp[j]);
5 }
6 }
7}
单调队列优化
对于每种物品都有
$dp[j] = \max(dp[j-v]+w,dp[j-2v]+2w,\cdots,dp[j-sv]+sw)$
$dp[j+v] = \max(dp[j]+w,dp[j-v]+2w,dp[j-2v]+3w,\cdots,dp[j-(s-1)v]+sw)$
可以看出 $dp[j]$ 后面的 $max$ 求值和 $dp[j+v]$ 的 $max$ 求值是有重复的，所有项全都加上一个 $w$ 最大值不变。只要对两端的项再处理一下即可。
复杂度 $\mathcal{O} (n^2)$
1for(int i = 1; i <= n; i++) { //第 i 种物品
2 for(int k = 0; k < v[i]; k++) { //余数从 0 to v[j]-1
3 deque<Pack> Q; //单调递减队列
4 for(int j = k, ord = 1; j <= C; j+=v[i], ord++) { //dp[j] 为 j 容量的背包最大价值
5 int value = dp[j] - ord*w[i];
6 while(!Q.empty() && Q.back().value <= value) Q.pop_back();
7 Q.push_back(Pack(value, ord));
8 if(ord - Q.front().order > s[i]) Q.pop_front(); //个数超出
9 dp[j] = Q.front().value + ord*w[i];
10 }
11 }
12}