背包九讲关于动态规划

背包问题九讲 v1.0

目录

第一讲 01

背包问题

第二讲 完全背包问题

第三讲 多重背包问题

第四讲 混合三种背包问题

前言

本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这

个计划的内容是写作一份较为完善的 NOIP 难度的动态规划总结，名为《解动

态规划题的基本思考方式》。现在你看到的是这个写作计划最先发布的一部分。

背包问题是一个经典的动态规划模型。它既简单形象容易理解，又在某种程度

上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例

题，我也将它放在我的写作计划的第一部分。

读本文最重要的是思考。因为我的语言和写作方式向来不以易于理解为长，思

路也偶有跳跃的地方，后面更有需要大量思考才能理解的比较抽象的内容。更

次比较重大的版本更新都会在这里发贴公布。

目录

第一讲 01

这是最基本的背包问题，每个物品最多只能放一次。

第二讲 完全背包问题

第二个基本的背包问题模型，每种物品可以放无限多次。

第六讲 分组的背包问题

一种题目类型，也是一个有用的模型。后两节的基础。

第七讲 有依赖的背包问题

另一种给物品的选取加上限制的方法。

第八讲 泛化物品

我自己关于背包问题的思考成果，有一点抽象。

第九讲 背包问题问法的变化

试图触类旁通、举一反三。

附： USACO

他们每人都最先指出了本文第一个 beta 版中的某个并非无关紧要的错误。谢

谢你们如此仔细地阅读拙作并弥补我的疏漏。

感谢 XiaQ，它针对本文的第一个 beta 版发表了用词严厉的六条建议，虽然我

只认同并采纳了其中的两条。在所有读者几乎一边倒的赞扬将我包围的当时，

你的贴子是我的一剂清醒剂，让我能清醒起来并用更严厉的眼光审视自己的作

品。

当然，还有用各种方式对我表示鼓励和支持的几乎无法计数的同学。不管是当

深深钦佩你们身上体现出的自由软件的精神，没有你们的感召，我不能完成本

文。在你们的影响下，采用自由文档的方式发布本文档，也是我对自由社会事

业的微薄努力。

P01: 01 背包问题

题目

有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c[i]，价值是 w[i]。

求解将哪些物品装入背包可使价值总和最大。

基本思路

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

用子问题定义状态：即 f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以

入容量为 v 的背包中”，价值为 f[i-1][v]；如果放第 i 件物品，那么问题就转化

为“前 i-1 件物品放入剩下的容量为 v-c[i]的背包中”，此时能获得的最大价值就

是 f[i-1][v-c[i]]再加上通过放入第 i 件物品获得的价值 w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为 O(N*V)，其中时间复杂度基本已经不能再

优化了，但空间复杂度却可以优化到 O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i=1..N，每次算出来

二维数组 f[i][0..V]的所有值。那么，如果只用一个数组 f[0..V]，能不能保证

第 i 次循环结束后 f[v]中表示的就是我们定义的状态 f[i][v]呢？f[i][v]是由 f[i-

1][v]和 f[i-1][v-c[i]]两个子问题递推而来，能否保证在推 f[i][v]时（也即在第

其中的 f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 f[i]

[v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的 f[v-c[i]]就相当于原来的 f[i-

1][v-c[i]]。如果将 v 的循环顺序从上面的逆序改成顺序的话，那么则成了 f[i]

[v]由 f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题 P02

简捷的解决方案，故学习只用一维数组解 01 背包问题是十分必要的。

事实上，使用一维数组解 01 背包的程序在后面会被多次用到，所以这里抽象

出一个处理一件 01 背包中的物品过程，以后的代码中直接调用不加说明。

过程 ZeroOnePack，表示处理一件 01 背包中的物品，两个参数

cost、weight 分别表明这件物品的费用和价值。

注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成

v=V..0 是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复

题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。

一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它

f[1..V]均设为-∞，这样就可以保证最终得到的 f[N]是一种恰好装满背包的最优

解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将

f[0..V]全部设为 0。

为什么呢？可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放

入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包

可能被价值为 0 的 nothing“恰好装满”，其它容量的背包均没有合法的解，属

于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么