Dynamic Programming

引入

有 个物品和一个容量为 的背包，每个物品有重量 和价值 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

由于每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为「0-1 背包问题」。

0-1背包

解释

例题中已知条件有第 个物品的重量 ，价值 ，以及背包的总容量

设：DP 状态 为在只能放前 个物品的情况下，容量为 的背包所能达到的最大总价值

考虑转移。 假设当前已经处理好了前 个物品的所有状态，那么对于第 个物品，

• 当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 ；

• 当其放入背包时，背包的剩余容量会减小 ，背包中物品的总价值会增大 ，故这种情况的最大价值为 。

由此可以得出状态转移方程：

由于对 有影响的只有 ，可以去掉第一维，直接用 来表示处理到当前物品时背包容量为 的最大价值，得出以下方程：

务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的

完全背包

解释

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

我们可以借鉴 0-1 背包的思路，进行状态定义：设 为只能选前 个物品时，容量为 的背包可以达到的最大价值。

需要注意的是，虽然定义与 0-1 背包类似，但是其状态转移方程与 0-1 背包并不相同。

过程

可以考虑一个朴素的做法：对于第 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 的。

状态转移方程如下

考虑做一个简单的优化。可以发现，对于 ，只要通过 转移就可以了。因此状态转移方程为：

与 0-1 背包相同，我们可以将第一维去掉来优化空间复杂度。如果理解了 0-1 背包的优化方式，就不难明白压缩后的循环是正向的（也就是上文中提到的错误优化）。

多重背包

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 个，而非一个。

一个很朴素的想法就是：把「每种物品选 次」等价转换为「有 个相同的物品，每个物品选一次」。这样就转换成了一个 0-1 背包模型，套用上文所述的方法就可已解决。状态转移方程如下：

时间复杂度 。

混合背包

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 次。

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了。下面给出伪代码：

二维费用背包

有 个任务需要完成，完成第 个任务需要花费 分钟，产生 元的开支。

现在有 分钟时间， 元钱来处理这些任务，求最多能完成多少任务。

这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间），只需在状态中增加一维存放第二种价值即可。

这时候就要注意，再开一维存放物品编号就不合适了，因为容易 MLE。

分组背包

有 件物品和一个大小为 的背包，第 个物品的价值为 ，体积为 。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。

这种题怎么想呢？其实是从「在所有物品中选择一件」变成了「从当前组中选择一件」，于是就对每一组进行一次 0-1 背包就可以了。

再说一说如何进行存储。我们可以将 表示第 组的第 件物品的编号是多少，再用 表示第 组物品有多少个。

有依赖的背包

小明有 元钱，想要买 个物品，第 件物品的价格为 ，重要度为 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。

目标是让所有购买的物品的 之和最大。

考虑分类讨论。对于一个主件和它的若干附件，有以下几种可能：只买主件，买主件 + 某些附件。因为这几种可能性只能选一种，所以可以将这看成分组背包。

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合。

泛化物品背包

这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为 的背包问题中，当分配给它的费用为 时，能得到的价值就是 。这时，将固定的价值换成函数的引用即可。

背包问题变种