01背包
描述
有N件物品, 背包容量为V, 每件物品 $i$ 耗费 $C_i$ , 得到的价值是 $W_i$ 。求解装入哪些物品使得价值总和最大。
公式
$F[i, v] = max \{ F[i - 1, v], F[i - 1, v - C_i] + W_i \}$
伪代码
$F[0, 0…V] \leftarrow 0$
$for\ i \leftarrow 1\ to\ N$
$for\ v \leftarrow C_i\ to\ V$
$F[i, v] \leftarrow max \{F[i-1,v], F[i-1,v-C_i]+W_i\}$
优化空间复杂度
$F[0…V] \leftarrow 0$
$for\ i \leftarrow 1 to N$
$for\ v \leftarrow V\ to\ C_i$
$F[v] \larr max\{F[v], F[v - C_i] + W_i\}$
抽象01背包问题
$def\ ZeroOnePack(F, C, W)$
$for\ v \larr V\ to\ C$
$F[v] \larr max(F[v], F[v-C] + W)$
完全背包
描述
N件物品, 背包容量为V, 每种物品都有无限件可用，每件物品 $i$ 耗费 $C_i$ , 得到的价值是 $W_i$ 。求解装入哪些物品使得价值总和最大。
公式
$F[i, v] = max\{F[i-1, v-kC_i] + kW_i|0\le kC_i \le v\}$
简单优化
若 $C_i \le C_j$ 并且 $W_I\ge W_j $，则去掉物品j, 不用考虑
转换为01背包求解
考虑到第 $i$ 种物品最多选$\lfloor V / C_i \rfloor$ 件， 于是将第 $i$ 种物品转化为 $\lfloor V/C_i\rfloor$ 件费用及价值均不变的物品，然后求解01背包问题
$O(VN)$ 的算法
$F[0..v]\leftarrow 0$
$for\ i \leftarrow 1\ to\ N$
$for\ v \larr C_i\ to\ V$
$F[v] \larr max(F[v], F[v-C_i] +W_i)$
抽象完全背包问题
$def\ CompletePack(F, C, W)$
$for\ v \larr C\ to\ V$
$F[v] \larr max\{F[v], F[v- C] +W\}$
