著名的背包问题：01背包问题

01背包问题

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，$N$，$V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i$,$w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围

$0 < N$, $V \leq 1000$

$0 < v_i$, $w_i \leq 1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

S

基本思路

  这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：

即$f[i][v]$表示前$i$件物品恰放入一个容量为$v$的背包可以获得的最大价值。则其状态转移方程便是：

$$f[i][v] = max \begin{cases} f[i-1][j] \\ f[i-1][j-c[i]] + w[i] \end{cases}$$

  这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前$i$件物品放入容量为$v$的背包中”这个子问题，若只考虑第$i$件物品的策略（放或不放），那么就可以转化为一个只牵扯前$i-1$件物品的问题。如果不放第$i$件物品，那么问题就转化为“前$i-1$件物品放入容量为$v$的背包中”；如果放第$i$件物品，那么问题就转化为“前$i-1$件物品放入剩下的容量为$v-c[i]$的背包中”，此时能获得的最大价值就是$f=[i-1][v-c[i]]$再加上通过放入第$i$件物品获得的价值$w[i]$。

总结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

• 01背包问题
• 完全背包问题
• 多重背包问题
• 混合背包问题
• 维费用的背包问题
• 分组背包问题
• 背包问题求方案数
• 求背包问题的方案
• 有依赖的背包问题

To be continue