动态规划算法经典例题_详解动态规划算法经典问题——零一背包

落日映苍穹つ 2023-01-12 11:34 179阅读 0赞

今天是周三算法与数据结构专题的**第12篇**文章，动态规划之零一背包问题。

在之前的文章当中，我们一起探讨了二分、贪心、排序和搜索算法，今天我们来看另一个非常经典的算法——**动态规划**。

在acm-icpc竞赛领域，动态规划是一个非常大的范畴，当中包含了许多变种，而且很多变种难度极大。比如在各种树上和图上以及其他数据结构上做动态规划，这会使得问题非常复杂。好在非竞赛选手并不需要了解到那么深入，一般来说，吃透背包九讲，就足够笑傲各种面试了。所以周三的算法专题我们开始全新的篇章——**背包系列**，今天和大家分享背包九讲中的第一讲，也是最简单的零一背包问题。

## 背包和零一背包 ##

没有竞赛经验的同学在看到这个标题的时候可能会一头雾水，动态规划和背包有什么关系。其实没有关系，我也不是陈奕迅的粉丝，只是当初最经典的动态规划问题用背包做了题面，还引发出了各种变种。后来在教学的时候为了方便，于是沿用了前人的名称。

之前我们在怪盗基德偷宝石的问题当中提到过背包问题，其实很简单，就是说我们当下有一个容量是V的背包，和n个体积分别是v\[i\]，价值是w\[i\]的物品。请问，在背包容量允许的前提下，我们**最多能够获得多少价值的物品**？

由于每种物品只有一个，也就是物品只有拿和不拿两种状态，所以这个问题被称为**零一背包问题**。

## 贪心与反例 ##

这种问题我们最先想到的就是贪心法，比如优先拿价值大的物品，或者是性价比高的物品，但是我们很容易构思出反例。

举个例子，比如背包的容量是10，我们有3个物品，体积分别是6，5，5，价值是10，8，8。这个反例可以证明两种贪心策略都不生效，因为价值最大的是10，它的体积是6，我们一旦拿了它就没有空间再继续获取其他物品，而显然拿两个5的情况是最优的。同样，体积是6的物品也是性价比最高的，性价比优先的贪心策略同样不生效。

实际上不仅这两种贪心策略不生效，**所有能够想到的贪心策略都不生效**。这个问题看起来简单，但是并不是那么容易解决。实际上这个问题一直困扰着计算学家，直到上世纪六十年代，动态规划算法横空出世，完美地解决了这个问题。

## 动态规划 ##

动态规划算法的英文是**dynamic programming**，算是很直白的翻译了。规划我们都很好理解，但是动态应该怎么理解呢？又怎么来动态地规划呢？关于这个问题的思考直接关系到算法的本质。

动态规划算法的本质是状态的记录和转移，我们结合刚才的问题，有没有想过**为什么贪心算法不可行**？其实很简单，因为我们没办法确定背包什么状态是完美的。虽然我们知道背包的容量是V，但是我们并不知道最优的情况下我们能装多少，最优的结束状态是什么。我们把空间V看成了一个状态来进行贪心，贪心得到的结果是最优的，但是只是贪心**能达到的状态的最优解**，并不是全局的最优解，因为背包容量的限制，很有可能我们贪心策略下无法达到真正最优的状态。

用刚才的例子解释一下上面这段话，在贪心算法下，我们会选取容量是6，价值是10的物品，这个物品拿取了之后背包的状态是6，获取的价值是10。这个状态是贪心能够达到的最终状态，对于这个状态而言，它是最优解，但是这个状态并不是整体最优的情况，因为在贪心策略下，无法达到容量10全用完的状态。

理解了这个问题之后，再去推导解法就顺其自然了。贪心策略可以获取一些状态最优的情况，那么我们**能不能记录下所有状态能够达到的最优的情况**，最后在这些最优的情况当中选取一个最优的，它不就是整体最优解了吗？

动态规划正是基于上述思路展开的，它解决的不是一个状态的最优解，而是所有状态的最优解。

## 状态与转移 ##

看到这里，你肯定还没理解动态规划算法，但是应该已经有一些大概的感觉了。这是对的，有正确的感觉是正确认识的前提。我们循序渐进，再来看状态这个概念。

我们刚才提了这么多次，究竟状态是什么呢？这是一个比较抽象的概念，在不同的问题当中它有着不同的含义。在背包问题当中，状态指就的是**背包容量的使用情况**。由于背包问题中物品的体积是整数，显然背包容量的可能性是有限的，这点不起眼，但是很重要，如果状态不是整数，那么虽然存在动态规划的可能，但是代码实现可能比较麻烦。

明白了背包的容量是状态之后，我们可以进一步想明白，背包的容量是会变化的。变化的原因是因为我们往里面放了东西，放了东西之后，背包的状态会发生变化，**会从一个状态转移到另一个状态**。状态的转移中间伴随着我们放入东西，我们放的物品并不是固定的，而是有多种选择的，我们决定放入A而不是BC，这是一种决策，**决策会带来状态的转移**，不同的决策会带来不同的转移。

比如当前有一个背包，它的容量是10，我们在其中已经放入了一个体积是3，价值是7的物品。如果这个时候，我们经过选择再放入一个体积是4，价值是5的物品。那么显然，背包占用的容量会变成7，价值会变成12。这个过程就是一个经典的状态转移过程，这也是整个动态规划算法的核心。

基本的概念和思想已经介绍完了，接下来就是用这些概念来解决实际问题了。

## 最优状态 ##

我们前文说了，动态规划最后会获取所有状态的最优解，再从中选取全局最优的。那么它是怎么获取局部最优解的呢？

在回答这个问题之前，我们先来思考两个问题。

首先，假如我们已经知道了背包体积是3时的最大价值是5，这时候我们决定放入一个体积是4，价值是5的物品，那么背包的体积会增加到7，那么这个时候获得的是体积6的最优解吗？

这个问题不难回答，我们稍微想想就知道，很有可能不是。举个最简单的例子，假如我们有一个体积是7，价值是20的物品。那么显然要比放这两个物品更优。虽然状态3最多能获得价值5，状态7也可以由状态3转移得到，但是这并不一定是最优的。**也就是说最优的状态转移出去，并不一定也能得到其他状态的最优值**。

我们把问题反过来就不一样了，如果我们知道了体积6的最优解，并且还知道它是由体积等于4转移得到的，那么我们能不能确定体积4的状态也是对应的最优解？

这次的答案就变了，是正确的，因为如果体积4时还有更好的解法，那么体积6理应也会变得更好才对，这和我们的假设矛盾了。

我们总结一下上面的两个结论，也就是说**局部最优的情况转移出去并不一定是最优的，但是局部最优一定也是由其他局部最优的状态转移得到的**。这句话有点像绕口令，但是我觉得应该不难解释。就好比学霸去考试，不一定能考第一，但是考到第一的一定是学霸。局部最优就是学霸，转移就是考试。局部最优转移出去并不一定是转移之后状态的最优，有可能还有其他更好的转移策略，但是对于某个状态最优的情况而言，它一定也是从之前的某个最优状态转移得到的。

并且状态的转移也是**有顺序的**，比如在这题当中，背包当中放入了物品体积只可能增加，不可能减小，意味着状态只能从小的转移到大的。

我们捋一捋思路，已经很明确了，状态可以转移，状态的转移有顺序，局部最优一定是由其他局部最优转移得到的。由于我们并不知道当前的转移能否达到最优状态，所以我们**需要用一个数组或者是容器来记录所有状态历史上曾经达到过的最值**。最后从所有的最值当中再选出一个最值来，就是最后问题的解。

到这里，如果是一般的动态规划问题，已经解决了，但是零一背包还有一个细节需要考虑。

## 无后效性 ##

我们先来看下整个的计算流程，首先我们需要从最初状态开始，这个最初的状态很好办，就是背包是空的时候，这时候的价值是0，体积也是0，这也是它的最优状态，这个很好理解，因为我们不能无中生有。

所以我们从0开始转移状态，状态转移伴随着决策，在这题当中体现在选取不同的物品上。我们遍历物品，作为决策，再遍历能够应用这些决策的状态，就拿到了所有的状态转移。最后，我们用一个容器记录一下所有状态转移过程当中达到的局部最优解，于是就结束了。

这个过程看起来非常正常，没有任何异常，但实际上，问题来了。

我们还用刚才的题面举例，背包容量是10，3个物品，体积分别是6，5，5，价值是10，8，9。我们从0开始拿取第三个物品，转移到了状态5，此时的价值是9。这个时候，我们继续往后遍历的话还会遍历到状态5，它已经是拿取了物品3，价值9的信息了。因为一个物品只能拿一次，所以我们**不能再用物品3转移状态5，否则就违反了题意**。

你可能会说这个问题不难，我们可以在状态当中也记录之前做过的决策嘛，只要在决策的时候加一个判断就好了。

表上面看是因为物品不能重复拿的限制，实际上是因为我们的状态之间会有影响。也就是说我们前面做的决策很有可能影响后面的状态做决策，这种状态之间的前后影响称为**后效性**。显然在有后效性的场景下我们是不能使用动态规划算法的，并不是所有问题都可以通过加上判断解决，我们需要解决后效性这个本质问题，也就是说我们要想办法消除后效性。

在这个问题当中，这一点很容易做到。我们只需要控制一下状态和决策的遍历顺序，**将之前的决策与之后的决策分开**，使它们互不影响即可。如果我们先遍历状态，再遍历每个状态可以采取的措施，这样必然会造成前后影响。因为前面做了的决定，后面就不能再做。但是后面并不能感知前面究竟做了什么决定。所以比较好的方法是先遍历决策，再来遍历可以采取这个决策的状态。为了避免决策前后的互相影响，我们采取**倒序的方式遍历状态**。

我们举个例子，假设背包容量还是10，我们枚举的第一个物品体积是3，价值是5。我们倒叙遍历状态7到0，因为对于大于7的状态而言，并不能采取这个决策(总体积会超)。因为对于大于7的状态而言，我们不能采取这个决策(总体积会超过限制)，对于状态7而言，我们可以采取这个决策，转移到状态10。我们并不知道这样转移会不会达成最优，所以我们这样来记录：dp\[10\] = max(dp\[10\], dp\[3\] + 5).

我们接着遍历体积6，可以转移到状态9。

由于我们是倒序遍历，所以当我们用状态7更新状态10时，状态7本身并没有被这个决策更新过。即使后面我们在遍历到状态4时更新了状态7，也不会影响状态10的结果。因为是倒序遍历的，**我们不会再用同一个策略更新到状态10了**。如果是正序遍历，则无法避免。同样的物品，我们很有可能会出现，用状态1更新状态4，再用状态4更新状态7，再用状态7更新状态10的情况出现。而这种情况其实对应了使用了多个同样的物品，这就和题意矛盾了。

举个例子，假设有一个物品体积是2，它的价值是5。我们遍历状态0的时候，会更新状态2，我们遍历到了状态2，又用同样的物品更新了状态4，得到了10。那么对于状态4而言，它其实相当于拿了2个这个物品，也就是说被同一个决策更新了两次。但是我们的物品最多只有一个，显然就不对了。

![81bbea1f7d091233bc78f3b1ca7c52b6.png][]

动态规划当中因为无法判断当前枚举的状态的来源，所以不允许出现后效性，如果解决不了则不能使用动态规划。这也是动态规划最基本的原则，在这题当中，我们是巧妙变换了决策和状态枚举的过程，消除了后效性。在其他题目当中未必相同，我们需要根据实际情况进行判断。

如果你在做题思考的过程当中忘记了动态规划的前提，就想想零一背包当中拿取物品的情况。物品只有一个，只能拿一次。前面拿过了后面还能拿，就违反了后效性。

## 状态转移方程 ##

我们整理一下刚才关于状态转移的思路，有以下几点：

1.  我们从状态0开始，状态0的最优价值是0.
2.  考虑后效性的问题，确保没有后效性
3.  执行决策的时候，会发生状态转移，记录状态对应的最优解

在这个问题当中，**决策就是获取物品，状态就是背包容量**。由于拿取物品会引起背包容量变化，并且每个物品只有一个，为了避免产生后效性，我们需要先枚举决策，再枚举状态，保证每个决策只在每个状态上最多应用一次。在此过程当中，需要一直记录每个状态的最优解。

由于背包的容量是V，我们只需要用一个容量是V的数组就足够记录所有的状态。

![1bd62ddc955ccb6cd69bc6ba2dfe30ca.png][]

dp记录的是所有的状态，我们用max(dp\[v+i.v\], dp\[v\] + i.w)来更新dp\[v+i.v\]状态的值，由于当前的决策不一定比之前的更好，所以要加上max操作，保证每个状态记录下来的结果都是它最优的。当所有的状态的最优解都有了之后，显然整个问题的最优解也在其中了。

上面这个记录状态转移过程的式子叫做**状态转移方程**，它也是动态规划算法的核心概念。很多时候，在我们解动态规划问题的时候，会在草稿纸上推演状态转移方程。如果状态转移方程能清楚地列出来，距离写出代码也就不远了。

## 代码 ##

上面的转移方程已经非常接近最后的代码了，真正写出来也就只有几行而已：

![750eb7d823658ba057996e6fbbc98472.png][]

## 总结 ##

关于零一背包的前后推导以及当中所有的概念始末就算是介绍完了，虽然我们用了这么多篇幅来介绍这个算法，但是真正写成代码也就只有短短几行。单从代码行数来看，动态规划可以说是实现代码最短的算法了，只是虽然它代码不长，但是思路并不简单，尤其是当中的下标以及循环的顺序等细节，希望大家不要掉以轻心。

今天零一背包的问题到这里就结束了，下周的算法专题我们继续背包问题，来看看01背包的进阶版——**完全背包和多重背包**问题，敬请期待。

如果觉得有所收获，请顺手点个**关注或者转发**吧，你们的举手之劳对我来说很重要。

[81bbea1f7d091233bc78f3b1ca7c52b6.png]: /images/20221119/37fd73d6f12b48fa97a7e3f939487e4d.png
[1bd62ddc955ccb6cd69bc6ba2dfe30ca.png]: /images/20221119/d3729a39a3aa45ccb361f96252d37418.png
[750eb7d823658ba057996e6fbbc98472.png]: /images/20221119/b8c7c9b0946c4a7dbcb16d2977f1284e.png