背包

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] \leftarrow max\{F[v], F[v - C_i] + W_i\}$

抽象01背包问题

$def\ ZeroOnePack(F, C, W)$

$for\ v \leftarrow V\ to\ C$

$F[v] \leftarrow 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 \leftarrow C_i\ to\ V$

$F[v] \leftarrow max(F[v], F[v-C_i] +W_i)$

抽象完全背包问题

$def\ CompletePack(F, C, W)$

$for\ v \leftarrow C\ to\ V$

$F[v] \leftarrow max\{F[v], F[v- C] +W\}$