动态规划求解0/1背包问题，0-1背包问题动态规划算法伪代码

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

在上一篇文章中，我们讨论了二分法、贪心算法、排序和搜索算法。今天我们来讨论另一个非常经典的算法——动态规划。

在acm-icpc竞赛领域，动态规划是一个非常大的范畴，有很多变体，而且很多变体都非常难。例如，对各种树、图和其他数据结构执行动态编程会使问题变得非常复杂。幸运的是，非竞争对手不需要了解那么多细节。一般来说，如果你完全理解了背包旅行的9个教训，你就有足够的信心面对任何类型的面试。因此，对于周三的算法主题，我们将开始—— 背包系列的新篇章。今天我将分享我的九个背包讲座的第一部分。这也是最简单的零一背包问题。

背包和零一背包

没有竞技经验的同学看到这个标题，可能会很困惑动态规划和背包有什么关系。其实我不是陈奕迅的粉丝。然而，最经典的动态规划问题是在背包中创建的，这导致了许多变化。后来为了教学方便，就开始沿用前人的名字。

背包问题，我之前在怪盗小子偷珠宝问题中提到过，其实很简单。也就是说，我们目前有一个体积为V 的背包和一个体积为v[i] 和n 值的背包。 w[i] 中的项目。那么我想问一下，在你的背包容量的情况下，你能获得的物品最大价值是多少？

这个问题被称为零一背包问题，因为每种类型只有一个物品，并且一个物品只有两种状态：已检索和未检索。

贪心与反例

这类问题首先想到的就是优先考虑价值高或者性价比高的东西之类的贪心法，但是很容易想到反例。

例如，如果你的背包容量为10，则有3件物品，容量为6、5、5，值为10、8、8。这个反例可以证明这两种贪心策略都不起作用。因为最大的值是10，它的体积是6。一旦你得到它，就没有空间继续得到其他物品，所以显然得到两个5 是最好的。的。同样，第六卷的物品也是性价比最高的，优先考虑性价比的贪婪策略也行不通。

事实上，不仅这两种贪婪策略无效，所有可能的贪婪策略也无效。这个问题虽然看似简单，但解决起来却并不那么容易。事实上，这个问题一直困扰着计算科学家，直到20 世纪60 年代，动态规划算法的出现彻底解决了这个问题。

动态规划

动态规划算法的英文名称是dynamicprogramming，很直译。我们都很好理解规划，但是我们如何理解动态呢？思考这个问题直接关系到算法的本质。

动态规划算法的本质是状态记录和传递。结合前面的问题，你有没有想过为什么贪心算法会失败？其实很简单，因为没有办法确定背包处于什么状态。我们知道背包的容量为V，但我们不知道在最佳条件下它能容纳多少东西，也不知道最佳的最终状态是多少。空间V可以认为是贪婪状态，但只是贪婪所能达到的状态的最优解，由于背包容量有限，这是非常困难的。也许我们的贪婪策略不允许我们真正达到最佳状态。

让我们用前面的例子来解释上面的段落。在贪心算法下，选择容量为6、值为10的项目。获得该物品后，背包状态为6，获得的价值为10。这个状态是贪婪所能达到的最终状态。然而，这总体上并不是最优情况，因为贪婪策略无法达到容量10 被充分利用的状态。

一旦理解了问题，自然就会想出解决方案。既然贪心策略可以得到多种最优情况，那么能否记录所有状态能够达到的最优情况，并最终在这些最优情况中选择最优的呢？

动态规划就是基于上述思想而发展起来的，它不是求解一种状态的最优解，而是寻求所有状态的最优解。

状态与转移

看完这个你不需要了解动态规划算法，但你应该已经有了一些感觉。是的，拥有正确的感受是正确理解的前提。让我们逐步了解一下状态的概念。

我已经多次提到过这一点，但目前的情况如何呢？这是一个比较抽象的概念，对于不同的问题有不同的含义。在背包问题中，状态指的是背包容量的使用情况。由于背包问题中物品的体积是整数，显然背包的容量可能性是有限的，但是如果状态不是整数，则动态规划是可能的，但这非常重要。代码实现可能很麻烦。

一旦你理解了背包容量是一种状态，你就可以进一步理解背包容量是可以改变的。它改变的原因是，当你把东西放进去之后，背包的状态发生了变化，从一种状态变成了另一种状态。当我们插入一些东西时就会发生状态转换。我们投入的东西并不是固定的，有很多选择。这是一个决定，该决定会导致状态转换。不同的决策会导致不同的转移。

例如，您当前有一个容量为10 的背包，并且您在其中放置了一个容量为3、价值为7 的物品。此时，选择并插入体积为4、值为5的项目。所以当然背包占用的空间是7，值为12。这个过程是一个经典的状态转移过程，也是整个动态规划算法的核心。

我们已经介绍了基本概念和想法。下一步就是运用这些概念来解决实际问题。

最优状态

前面提到，动态规划最终得到所有状态的最优解，然后选择全局最优解。那么，如何才能得到局部最优解呢？

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

首先，如果您知道容量为3 的背包的最大值为5，并且您决定添加一个容量为4、值为5 的物品，则背包的容量将为。如果我们增加到7，此时我们得到的是第6卷的最优解？

这个问题并不难回答。如果你想一下，你就会发现事实可能并非如此。在最简单的示例中，考虑一个体积为7、价值为20 的物品。那么显然比包含这两个要好。在状态3中，可以获得最大值5，但是从状态3转变也可以获得状态7，但这不一定是最优的。换句话说，转移最优状态并不一定会导致其他状态的最优值。

问题反过来，如果我们知道卷6的最优解，并且知道它是通过转移卷4得到的，那么我们是否可以确定卷4的状态也是对应的最优解呢？

这次答案改变了并且是正确的。这意味着如果第4 卷有更好的解决方案，那么第6 卷也应该更好。这与我们的假设相反。

让我们总结一下上面的两个结论。也就是说，一个局部最优值的传递不一定是最优的，但该局部最优值还必须是通过其他局部最优值的传递得到的。这句话有点绕口令，但我觉得解释起来并不难。就像一个优等生参加考试一样。你不一定能考第一名，但获得第一名的人一定是尖子生。局部最优是学术硕士，转学是考试。局部最优转移不一定是转移后的最优状态。可能存在其他更好的转移策略，但为了使特定状态达到最佳状态，它还必须从先前的最佳状态转移。

而且，状态转换是连续的。例如，在这道题中，背包中放置的物品数量可以增加，但不能减少。也就是说，国家只能从小到大过渡。

考虑到这一点，很明显状态是可转移的，状态的转移是顺序的，并且局部最优必须通过转移其他局部最优来获得。由于我们不知道当前的转换是否可以达到最佳状态，因此我们需要使用数组或容器来记录所有状态历史上达到的最高值。最后从所有最佳值中选出一个最佳值，成为最终问题的解。

至此，我们已经解决了一般的动态规划问题，但是使用ZeroOne Backpack 还有一个细节需要考虑。

无后效性

首先我们看一下整个计算过程。我们需要从这个初始状态开始，即背包为空时的值。体积也为0。这也是一个最佳的情况。你不能无中生有。

因此，状态转移是从0开始的。状态转移涉及决策。这反映在该问题的各个项目的选择上。将项目作为决策进行遍历，然后遍历这些决策可以应用到的状态，并获取所有状态转换。最后，我们使用一个容器来记录每个状态转换过程中达到的局部最优，这样就完成了。

虽然这个过程看起来很正常很正常，但其实是有问题的。

另外，在上一个问题的示例中，背包容量为10，体积为6、5 和5，值为10、8 和9。获取从0 开始的第三项，并将其移动到状态5，其中值为9。此时，如果我们继续遍历，我们将遍历到状态5，此时我们已经获得了第3项和第9项的有价值信息。物品3 不能再用于转移状态5，因为该物品只能获得一次。否则就违反了问题的意思。

这个问题看上去可能并不困难。另外，你只需要在做决定时添加一些判断即可。

表面上看，这是由于物品不能重复获得的限制，但实际上，这是由于地位的影响。也就是说，过去做出的决策可以影响下一个状态的决策。这些状态之间的来回效应称为后效应。显然，动态规划算法不能用于有后遗症的场景。并不是所有的问题都可以通过增加判断力来解决。也就是说，你需要找到一种方法来消除后遗症。

在这个问题中，这很容易做到。您需要做的就是控制状态和决策通过的顺序，并将先前的决策与后续的决策分开，以便它们不会相互影响。首先是跨州，然后是每个州采取的行动，不可避免地会产生来回的影响。因为你无法撤销已经决定的事情。然而，后者无法识别之前做出的决定。因此，更好的方法是先看决策，然后再看哪些状态可以做出这个决策。为了避免决策前后的交叉影响，我们以相反的顺序跟踪状态。

例如，假设背包容量仍为10，则您枚举的第一个项目的体积为3，值为5。由于对于大于7 的状态无法做出此决定（将超出总量），因此我们回顾并查看状态7 到0。对于大于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实际上相当于得到了这个物品的两个。这意味着它会以相同的决定更新两次。但是，最多可以有一项。这显然是错误的。

动态编程无法确定当前枚举状态的来源，因此如果无法解析它，则不能使用动态编程。这也是动态规划最基本的原理，在这个问题中我们巧妙地修改了决策和状态枚举的过程，消除了后遗症。其他科目不一定如此，应根据实际情况确定。

如果你在思考问题时忘记了动态规划的前提，请考虑从零一背包中取出物品的情况。物品只有一件，并且只能获得一次。如果先服后服，则违反后效。

状态转移方程

如果整理一下目前关于状态转换的思考，有以下几点。

我们从状态0开始，状态0的最优值为0。考虑后效问题，保证在执行无后效决策时存在状态转移，并记录该状态对应的最优解。

在这个问题中，决策是获取物品，状态是背包的容量。由于拿取物品会改变背包的容量，并且每个物品只有一个物品，为了避免副作用，我们首先枚举决策，然后枚举状态，并且每个决策添加到每个状态中都需要确保。它仅适用。最多一次。这个过程需要不断记录每个状态的最优解。

由于背包的容量为V，我们可以简单地用一个容量为V的数组来记录所有的状态。

dp 记录所有状态。要更新dp[v+i.v] 状态的值，请使用max(dp[v+i.v], dp[v] + i.w)。因此，当前的决定并不一定比之前的决定更好。为了保证每个状态记录的结果都是最优的，我们需要添加一个max操作。显然，如果所有状态的最优解都有，那么整个问题的最优解也在其中。

上面记录状态转移过程的方程称为状态转移方程，也是动态规划算法的核心概念。在解决动态规划问题时，我们经常在纸上推导状态转移方程。如果你能清楚地列出状态转移方程，用不了多久你就可以编写代码了。

代码

上面的传递方程与最终代码非常接近，只需要编写几行。

总结

现在我们已经导出了ZeroOne Backpack并介绍了其中的所有概念，我们花了很多篇幅来介绍这个算法，但实际上只写了几行代码。单从代码行数来说，动态规划可以说是代码最短的算法，但是虽然代码没有那么长，但是思想却并不简单，尤其是涉及到下标和命令。不要低估循环。

今天的零一背包问题到这里就结束了。下周的算法主题将讨论01 背包、—— 完整背包以及多背包问题的演变版本。

如果您觉得有所收获，请关注或转发。你的微小努力对我来说非常重要。