背包九讲读书笔记
0-1 背包问题
基本题目套路
有 N 件物品和一个容量为 V 的背包，放入第 i 件物品消耗的费用是 Ci， 得到的价值是 Wi。 求解将哪些物品装入背包，可使总价值总和最大。
基本题目思路
- 特点：每件物品只有一个，选择：
放 or 不放。
- 子问题：
F[i, v]： 前 i 件物品恰好放入容量 v 的背包，可以获得的最大价值
- 状态转移：
F[i, v] = max{F[i-1, v], F[i-1, v-Ci] + Wi}
- 当前的价值，只和之前的价值有关，因此两个选择下的价值为：
- 如果
i 不选，价值：前 i-1 件，放入容量 v 的背包（F[i-1, v]）
- 如果
i 选择，价值：前 i-1 件，放入容量（v-Ci）的背包（确保 i 能放下去，得减去 i 占用的容量）+ 放入 i 的价值 Wi
伪代码
1
2
3
4
| F[0, 0..V] <- 0
for i <- 1 to N
for v <- Ci to V
F[i, v] <- max{F[i-1, v], F[i-1, v-Ci] + Wi}
|
优化
时间复杂度：O(VN)
空间复杂度：滚动数组（逆序计算 F[v]，才能保证正确的顺序）
1
2
3
4
| F[0..V] <- 0
for i <- 1 to N
for v <- V to Ci
F[v] <- max{F[v], F[v-Ci] + Wi}
|
1
2
3
| def ZeroOnePack(F,C,W)
for v <- V to C
F[v] <- max(F[v], F[C-v] + W)
|
1
2
3
| F[0..V] <- 0
for i <- 1 to N
ZeroOnePack(F,Ci,Wi)
|
完全背包问题
题目基本套路
N 种物品和容量为 V 的背包，每种物品都有无限件可以用，放入第 i 件物品消耗的费用是 Ci， 得到的价值是 Wi。 求解将哪些物品装入背包，可使物品总消耗费用不超过背包容量，且价值总和最大。
基本套路
- 每种物品无限件，因此每个物品的策略不是：选和不选。而是
选几件
- 状态转移：
F[i, v] = max{F[i-1, v-kCi] + kWi | 0 ≤ kCi ≤ v}
简单有效的优化
- 若两件物品
i, j 满足 Ci ≤ Cj 且 Wi ≥ Wj，则可以将 j 直接去掉，不用考虑 (任何情况下，都可以将价值小费用高的 j 换成物美价廉的 i)
- 或者 将费用大于 V 的物品去掉
转换为 0-1 背包问题
- 第 i 种物品最多选：V/Ci 种，把第 i 种物品转化为 V/Ci 件费用及价值不变的物品。 （将一种物品转化为多件只能选 0 或者 1 件的 0-1 背包问题）
- 二进制：第 i 种物品拆成费用为 Ci2^k，价值为 Wi2^k 的若干件物品。 k 满足 Ci2^k ≤ V 的非负整数。
