背包九讲

写在前面

随缘更新

1、01背包问题

题目

有 $N$ 件物品和一个容量为 $V$ 的背包。放入第$i$件物品花费的费用是 $c[i]$ ，得到的价值是 $w[i]$ ，求将哪些物品装入背包可使价值总和最大。

思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 $f[i][j]$ 表示前 $i$ 件物品恰放入一个容量为 $j$ 的背包可以获得的最大价值（这里原文中使用了“恰”，但实际并不需要正好装满，在初始化可以区分开这两种情况，下文有提及）。则其状态转移方程便是：

$f[i][j]=max(f[i−1][j] , f[i−1][j−c[i]] + w[i])$

“将前 $i$ 件物品放入容量为 $j$ 的背包中”这个子问题，若只考虑第 $i$ 件物品的策略（放或不放），那么就可以转化为一个只牵扯前 $i−1$ 件物品的问题。

如果不放第 $i$ 件物品，那么问题就转化为“ $i−1$ 件物品放入容量为 $j$ 的背包中”，最大价值为 $f[i−1][j]$ ；如果放第 $i$ 件物品，那么问题就转化为“前 $i−1$ 件物品放入剩下的容量为 $j−c[i]$ 的背包中”，此时能获得的最大价值就是 $f[i−1][j−c[i]]$ 再加上通过放入第 $i$ 件物品获得的价值 $w[i]$。

优化

后续再更

2、完全背包问题

题目

有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品都有无限件可用。第 $i$ 种物品的费用是 $c[i]$ ，价值是 $w[i]$ 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

思路

本题相比于01背包增加了每件物品有无限件这一条件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 $0$ 件、取 $1$ 件、取 $2$ 件 $\cdots$ 等很多种。如果仍然按照解01背包时的思路，令 $f[i][j]$ 表示前 $i$ 种物品恰放入一个容量为 $V$ 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程：

$f[i][j]=max(f[i−1][j−k \times c[i]]+k \times w[i])∣0≤k \times c[i]≤j$