持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第31天，点击查看活动详情

动态编程 — 0/1背包问题

我们在第 14 章中看到的优化问题之一是 0/1 背包问题。回想一下，我们查看了一个贪婪的算法，该算法在 n log n 时间内运行，但不能保证找到最佳解决方案。我们还研究了一种蛮力算法，该算法可以保证找到最佳解决方案，但以指数时间运行。最后，我们讨论了这样一个事实，即问题在输入大小方面本质上是指数级的。在最坏的情况下，如果不查看所有可能的答案，就无法找到最佳解决方案。幸运的是，情况并不像看起来那么糟糕。动态规划提供了一种在合理的时间内解决大多数 o/1 背包问题的实用方法。作为推导此类解决方案的第一步，我们从基于穷举枚举的指数解决方案开始。关键思想是通过构造一个有根的二叉树来探索可能的解决方案的空间，该二叉树枚举满足权重约束的所有状态。

有根二叉树是一个无环有向图，其中

·只有一个节点没有父节点。这称为根。每个非根节点只有一个父节点。

·每个节点最多有两个子节点。无子节点称为叶。

0/1 背包问题的搜索树中的每个节点都标有四重，表示背包问题的部分解决方案。四重的元素是：

·一组要带走的物品

尚未作出决定的项目清单

要获取的项目集中项目的总值（这只是一种优化，因为可以从集合中计算值）

背包中的剩余空间。（同样，这是一个

优化，因为它只是允许的重量与到目前为止所有项目的重量之间的差异。

树是从根开始自上而下构建的。95 从尚待考虑的项目中选择一个元素。如果背包中有该物品的空间，则会构造一个节点，以反映选择拿走该物品的后果。按照惯例，我们将该节点绘制为左子节点。正确的孩子表明选择不服用该物品的后果。然后递归应用该过程，直到背包装满或没有更多要考虑的项目。因为每条边代表一个决策（采取或不采取一项），因此这种树称为决策树.96 Eigure 15-3 是描述一组项目的表。

Eigure 15-4 是一个决策树，用于在假设背包的最大重量为 5 的情况下决定携带哪些物品。树的根（节点 o）有一个标签 <{}， [a，b，c，d]， 0， 5>，表示没有采取任何项目，所有项目仍有待考虑，获取的项目值为 o，权重 5 仍然可用。节点 1 表示已采取项目 a，[b，c，d] 仍有待考虑，所获取项目的价值为 6，并且背包可以再装2磅。节点 1 没有左子项，因为重达 3 磅的物品 b 不适合背包。

在图 15-4 中，每个节点中冒号前面的数字表示可以生成节点的一种顺序。这种特殊的顺序称为左先深度优先。在每个节点上，我们尝试生成一个左节点。如果这是不可能的，我们尝试生成一个正确的节点。如果这也是不可能的，我们备份一个节点（到父节点）并重复该过程。最终，我们发现自己已经产生了根的所有后代，并且该过程停止了。当它这样做时，已经生成了可以放入背包的每个项目组合，并且任何具有最大价值的叶节点都表示最佳解决方案。请注意，对于每个叶节点，第二个元素是空列表（指示没有更多要考虑占用的项目），或者第四个元素是 o（指示背包中没有剩余空间）。

不出所料（特别是如果你读了第14章），深度优先树搜索的自然实现是递归的。图 15：5 包含这样的实现。它使用类 Item 和图 14-2 中定义的函数。

该函数max_val返回两个值：所选项集和这些项的总值。它被调用有两个参数， 对应于树中节点标签的第二个和第四个元素：

to_consider。树中较高节点的那些项目

（对应于递归调用堆栈中的早期调用）尚未考虑。

利用。剩余可用空间量。

请注意，max_val 的实现不会构建决策树，然后查找最佳节点。相反，它使用局部变量结果来记录到目前为止找到的最佳解决方案。图 15-6 中的代码可用于测试max_val。

当运行smal1_test（使用图 15-3 中的值）时，它会打印一个结果，指示 Eigure 15-4 中的节点 8。是最佳解决方案：

这些函数生成许多项目，big_test可用于测试随机生成的项目集max_val。尝试big_test（10， 40）。这并没有花很长时间。现在尝试big_test（40，100）。在你厌倦了等待它返回之后，停止计算并问问自己发生了什么。

让我们考虑一下我们正在探索的树的大小。由于在树的每个级别，我们决定保留或不保留一个项目，因此树的最大深度是len（项目）。在级别o，我们只有一个节点，在级别1最多两个节点，在级别2最多四个节点，在级别3最多八个节点。在第 39 级，我们最多有 239 个节点。难怪要跑很长时间！

让我们看看动态规划是否有帮助。

最佳子结构如图 15-4 所示。以及图 15-5。每个父节点组合其子节点达到的解决方案，为根植于该节点的子树派生出最佳解决方案。

是否还有重叠的子问题？乍一看，答案似乎是“不”。在树的每个级别，我们都有一组不同的可用项目需要考虑。这意味着如果确实存在常见的子问题，它们必须位于树的同一级别。事实上，在树的每个级别，每个节点都有相同的项目集需要考虑。但是，我们可以通过查看图 15-4 中的标签来查看。某个级别的每个节点代表一组不同的选择，这些选择涉及树中较高位置的项。

考虑每个节点正在解决什么问题：从剩下的要考虑的项目中找出要采取的最佳项目，给定剩余可用重量。可用重量取决于迄今为止所带物品的总重量，但不取决于所带物品或所带物品的总价值。因此，例如，在图 15-4 中，节点 2 和节点 7 实际上正在解决相同的问题：在给定可用权重为 2 的情况下，决定应该采用 [c，d] 的哪些元素。

图 15-7 中的代码利用最优子结构和重叠子问题，为 0/1 背包问题提供基于记忆的动态规划解决方案。

def fast_max_val（to_consider， avail，memo ={}）：

“”“假设to_consider项目列表，利用递归调用提供的权重备忘录

返回 0/1 背包问题的解决方案的总值的元组以及该解决方案的项目“”“ if（len（to_consider）， avail） 在备忘录中：

添加了一个额外的参数 memo，以跟踪已解决的子问题的解决方案。是的，使用字典实现，该字典的键由要考虑的长度和可用权重构造而成。表达式 len（to_consider） 是表示仍待考虑的项目的紧凑方式。这是因为项目总是从列表to_consider的同一端（前面）删除。

现在，将 max_val 调用替换为 big_test 中的fast_max_val调用，并尝试运行 big_test（40， 100）。它几乎立即返回问题的最佳解决方案。

图 15-8 显示了我们对不同数量的项目和最大权重为 100 的问题运行代码时发出的调用次数。增长很难量化，但显然远低于指数级.97 但是，既然我们知道 0/1 背包问题在物品数量上本质上是指数级的，这怎么可能呢？我们找到推翻宇宙基本定律的方法了吗？不，但我们发现计算复杂性可能是一个微妙的概念

fast_max_val的运行时间由生成的不同对的数量决定，<to_consider，可用>。这是因为关于下一步做什么的决定仅取决于仍然可用的项目和已经采取的项目的总重量。

要考虑的可能值的数量由 len（项目）限制。可用值的可能数量更难表征。它由背包可以容纳的物品的最大不同重量总数从上面开始限制。如果背包最多可以容纳 n 件物品（基于背包的容量和可用物品的重量），则 vail 最多可以取 2 英寸的不同值。原则上，这可能是一个相当大的数字。但是，在实践中，它通常不会那么大。即使背包容量很大，如果从相当小的可能重量中选择物品的重量，许多套物品的总重量也会相同，从而大大减少了运行时间。该算法属于称为伪多项式的复杂性类。对这个概念的仔细解释超出了本书的范围。粗略地说，fast_max_val表示可用可能值所需的位数呈指数级增长。要查看从相当大的空间中选择 avai 值时会发生什么情况，请将图 15-6 中函数big_test中对 max_val 的调用更改为

当项目数为 1024 时，查找解决方案现在需要 1，028，403 次fast_max_val调用。

为了观察从巨大的空间中选择权重时会发生什么，我们可以从正实数而不是正整数中选择可能的权重。为此，请替换该行，

在 build_many_items 按行

每次调用它时，random.random（） 都会返回一个介于 o.o 和 1.0 之间的随机浮点数，因此对于所有意图和目的，无限数量的可能权重。不要屏住呼吸等待最后一项测试完成。动态规划可能是常识意义上的神奇技术，99。但它不能在礼仪意义上行神迹。