[动态规划] 《背包九讲》阅读笔记

1.01背包

题目与问题解决

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


过程 ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。

不同问题的初始化

有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。
前者需要除了F[0]为0，其它F[1\~V]均设为负无穷。后者F[1\~v]均为0。

一个常数优化

（亲测，这个常数优化效果极其小，还很容易写崩。。）

2.完全背包

题目与问题解决

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

01背包改进

背包问题的一些简单优化

1.任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。
2.首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以(V+N)地完成这个优化。
（同样很随缘）

转化为普通01背包的方法

考虑把完全背包问题转化为01背包问题来解。
考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。
这样给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。

二进制思想转换法：把第i种物品拆成费用为c[i]∗2k$c[i]\ast 2^k$、价值为w[i]∗2k$w[i]\ast 2^k$的若干件物品，其中k满足c[i]∗2k<=V$c[i]\ast 2^k<=V$。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2k$2^k$件物品的和。这样把每种物品拆成(logV/c[i])$(logV/c[i])$件物品，是一个很大的改进。

O(NV)算法

完全背包问题

3.多重背包

题目与解决方案（例题POJ1276）

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

优化方法：二进制

将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,… ,2k−1$2^{k-1}$,n[i]−2k+1$n[i]-2^k+1$，且k是满足n[i]−2k+1>0$n[i]-2^k+1>0$的最大整数。
例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
这样就将第i种物品分成了(logn[i])$(logn[i])$种物品，将原问题转化为了复杂度为O(V∗∑logn[i])$O(V\ast \sum logn[i])$的01背包问题，是很大的改进。
下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

比较难理解，纸上的演算如下：

4.混合三种背包问题

由于我们已经分别对三种背包做过抽象过程，所以就很easy了。


这里体现了编程种抽象的威力，当我们把一个个简单部分成功地抽象成过程以后，那么简单题的累积就不再是难题。

5.二维费用的背包问题

问题与解决方案

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。

然后根据前面的抽象过程，01背包的时候该逆序就逆序，完全背包的时候该顺序就顺序等等，题目可能会把这些结合起来。

物体总个数的限制

有些题目可能会对物体的总个数有个限制，其实只是变相的“二维费用”，加个维度表示已经用的物体个数即可。
换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。

小结

当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一纬以满足新的限制是一种比较通用的方法。

6.分组背包

题目与解决方案

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

注意此处的循环顺序，“for v=V..0”这一层循环必须在“for所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

7.有依赖的背包

简化的问题

这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

解决方案

1.考虑枚举所有方案，但这样做是指数级的复杂度。
2.考虑对于一个主件，所有决策互斥，就能考虑物品组，但决策复杂度仍没有边。
3.考虑02的“一个简单有效的优化”，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。
4.更复杂形式：依赖关系以森林的形式给出，利用接下来的泛化物品考虑树形DP。

8.泛化背包

此内容不是很理解，原文留下。

9.背包问题的其它问法

输出方案

方法1：按最后算出来的f(i)倒推递归即可。
方法2：记录动作。

输出字典序最小的最优方案

这里也不是很理解，放上原文。

求方案总数

对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，转移方程即为

初始条件f[0][0]=1。
这样可行的原因是因为可能性并行，求和即可。

最优方案的总数

求第k优解

基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。

这样实际就做到了枚举所有决策，求出其前k优值。

附录：用搜索做背包

（当作课外阅读即可。。）