0-1背包问题的动态规划算法

（给算法爱好者加星标，修炼编程内功）

来源：Bat特白

https://zhuanlan.zhihu.com/p/30959069

首先得知道什么是0-1背包问题（knapsack problem）

◆ 贼，夜入豪宅，可偷之物甚多，而负重能力有限，偷哪些才更加不枉此行？

◆ 抽象的话，就是：

给定一组多个（）物品，每种物品都有自己的重量（）和价值（），在限定的总重量/总容量（）内，选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高。

◆ ◆ 更加抽象的话：

给定正整数、给定正整数，求解0-1规划问题：

 ， s.t.  ，  。

◆ 示例应用：处理器能力有限时间受限，任务很多，如何选择使得总效用最大？

◆ 数值例子：如下图。

0-1背包问题的定性

◆ 对于一般性的0-1背包，

贪婪算法无法得到最优解。

反例，不多解释——

事实上它可能想多差有多差（以  作为“贪婪”的标准，也不多解释了）——

◆ 确定性问题版本的背包问题是NP的，

“，求使得 ”是Karp的21个NPC问题之一（实际上Karp的表述是现在所称的子集和（subset sum）问题）。

---

0-1背包问题的递推关系

定义子问题  为：在前  个物品中挑选总重量不超过  的物品，每种物品至多只能挑选1个，使得总价值最大；这时的最优值记作  ，其中  ，  。

考虑第  个物品，无外乎两种可能：选，或者不选。

• 不选的话，背包的容量不变，改变为问题  ；

• 选的话，背包的容量变小，改变为问题  。

最优方案就是比较这两种方案，哪个会更好些：

 。

得到

 。

---

“填二维表”的动态规划方法

算法就很自然了：

之前的例子填表的结果是——

（蓝色格子表示本行值发生变化的格子）

然后发生  时才会有“取第  件物品”发生。

所以从表格右下角“往回看”如果是“垂直下降”就是发生了  ，而只有“走斜线”才是“取了”物品。

这个算法的复杂度就很容易算了——每一个格子都要填写数字，所以时间复杂度和空间复杂度都是  。当"  "时（就不严谨地使用渐近分析的语言了），复杂度是  。

---

所谓“填一维表”的动态规划方法

◆ 其实呢，上面那个二维表，也可以用一行来存储啊！对不啦？

◆ 所以，根本的区别在于思想，而不是具体存储方式。

那么这个算法的思想又是什么呢？——其实就是：

• 每行都有些数值相同的哦，所以

• 只记录每行里那些不同的数值就好了啊。

◆ 例如上面的表格中，只记录蓝色的部分，

格式是（为了方便阅读，再贴一次图）：

 、

 、  、

 、  、  、  、

 、  、  、  、  、  、  、  、

……（不写了，累）

◆ 你会说，这也没省什么地方啊？！

的确，对于这个例子来说是这样的——要不然数值太大我画不下。

你假设每个  都扩大1000倍，那样的话，表格也扩大到1000倍，填表时间也增加到1000倍，然而蓝色的格子还是那么多。

◆ 好了，继续，下面有三个问题：

1.  ，  ；（这比较显然）

2. 什么时候会发生“  ”的情况？

3. 什么时候会发生“  ”的情况？

◆ ◆ ◆ ◆ 下面来看问题2，一定是发生了“容量扩大后有个新的东西可以放下了”！

所以固定  ，让  变化，  一定是“阶梯状”的：

• 有的  使得  ；

• 有的  使得  。

例如，前面例子中  如下图所示：

看下，是右移上移 。

所以  （  ）就是下述两条“阶梯”

在max意义下的“叠加”。

比较和 的“转折点”：

 的是  ；  的是  。

于是：

• 对于每一个  ，  最多只有  个“转折点”——因为  个物品，最多只有  个“选”、“不选”的组合；

•  中  那部分的所有可能的“转折点”就是由  的每个转折点  变为 ；（“可能”这个词后面再解释）

• 推而广之，  中  那部分的所有可能的“转折点”就是由  的每个转折点  变为  。

设置，则由得到的所有可能的“转折点”为 。

例如 ：

例如 ，  ：

这时有些问题：

1. 超过  的部分可以不用考虑；

2. 绿色的圆形里有些“转折点”被湮没了——这就是之前说的“可能”的意思。

来看哦，  。

于是  的所有可能应该是

Ok，首先删除掉第二分量大于  的（上图红框里）（称作第一类抛弃），得到

 。

然后按第二分量递增排序，得到：

按道理说，对于阶梯函数来说，如果第二分量是递增的，那么第三分量也应该是递增的。但是上图中红框里不是哦——事实上它们是“被湮没”的“转折点”（上图的黄色圆形）。

所以哦，弃掉他们（称作第二类抛弃），得到 ，就是下图 。

而最终结果就是 的最后一项的第三个分量。

由得到 的过程是（例如）：

已经按照第二分量递增排序好，

之后先写成

然后对第一个三元组，

删除当前位置之后被“湮没”的

对第二个三元组，一定是插入当前位置之后，并被立即“湮没”，

不断这样进行下去，并注意第一类抛弃即可得到  。

令，则可以得到（由于分行了，就不在乎三元组的第一分量了）：

然后所谓“一维”存储，其实就是把它“存储成了”一维，例如使用两个一维数组和一个start数组做“分割”：

◆ 然后就是如何得到方案——

看  的最后一个是不是与  的最后一个相同，相同的话就直接看  ；

 的最后一个与  的最后一个不同，所以一定拿了物品4，然后看  第二分量不超过5（=  ）的最后一个，是  ；

 与  的最后一个不同，所以一定拿了物品3；

……然后类推。

◆ 最后是分析复杂度：

路线是计算  的元素个数，然后对  求和，就得到了所有“蓝色格子”的数量。

然后，

• 首先，由于  在不考虑两类抛弃的情况下（最差情况就是不发生这两类抛弃），元素个数恰好等于  元素数的两倍；也可以这样来看——对于每一个  ，  最多只有  个“转折点”；

• 由  得到  时，  中各组的第二分量、第三分量一定彼此不同，那么每个  中的  的取值范围是  ，第三分量的取值范围是  。所以这样的三元组最多有  个。

对  求和，得到

•  ;

•  ；

而由  产生  的计算过程主要就是产生一个新的对、插入、删除（抛弃），所以这个过程的计算量是和  元素数成正比的。

所以得到，无论空间复杂度还是时间复杂度，都是  的。

即使  ，这时的算法复杂度也控制在  之内。

- EOF -

推荐阅读  点击标题可跳转

觉得本文有帮助？请分享给更多人

关注「算法爱好者」加星标，修炼编程内功

点赞和在看就是最大的支持❤️