使用动态规划解决背包问题的一个版本

Question

我正在通过 OpenCourseWare 上的 MIT6.0002（https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science -fall-2016/assignments/），我被问题集 1 的 B 部分难住了。这个问题是作为背包问题的一个版本提出的，表述如下：[奥克夫妇发现了一群能下不同重量金蛋的鹅]他们希望在旅途中携带尽可能少的蛋，因为他们的船上没有太多空间。他们已经详细记录了鹅可以在给定群中产下的所有鸡蛋的重量以及他们的船可以承载多少重量。在 dp_make_weight 中实现一个动态规划算法来找到为某艘船制造给定重量所需的最小鸡蛋数量。结果应该是一个整数，表示从给定的鹅群中获得给定重量所需的最小蛋数。您的算法不需要返回鸡蛋的重量，只需要返回最小数量的鸡蛋。假设： - 不同鹅之间的所有鸡蛋重量都是唯一的，但是一只给定的鹅总是会产下相同大小的鸡蛋——Aucks 可以等待鹅产下所需数量的鸡蛋[即每种大小的鸡蛋都有无限的供应]。- 总有 1 号的鸡蛋可用该问题还指出解决方案必须使用动态规划。我已经编写了一个解决方案（在 Python 中），我认为它找到了最佳解决方案，但它不使用动态编程，我无法理解动态编程是如何适用的。还建议解决方案应使用递归。任何人都可以向我解释在这种情况下使用记忆的好处是什么，以及通过实施递归解决方案我会得到什么？（如果我的问题太含糊，或者解决方案对文字来说太明显，我深表歉意；我是编程和这个网站的相对初学者）。

Answer 1

这里的问题是典型的 DP 情况，贪婪有时可以给出最优解，但有时不能。

这个问题的情况类似于经典的 DP 问题硬币找零，在给定目标值的情况下，我们希望找到最少数量的不同价值硬币来找零。在美国等一些国家（使用价值 1、5、10、25、50、100 的硬币）可用的面额是这样的，最好是贪婪地选择最大的硬币，直到价值低于它，然后继续下一个硬币。但是对于其他面额集合，如 1、3、4，反复贪婪地选择最大值会产生次优结果。

同样，您的解决方案适用于某些蛋重，但对其他蛋重无效。如果我们选择鸡蛋的权重为 1、6、9，并给出目标权重 14，算法会立即选择 9，然后无法在 6 上取得进展。此时，它会吞下一堆 1，最终认为是 6是最小的解决方案。但这显然是错误的：如果我们聪明地忽略 9 并先选择两个 6，那么我们可以只用 4 个鸡蛋达到所需的重量。

这表明我们必须考虑这样一个事实，即在任何决策点，采用我们的任何面额都可能最终导致我们获得全局最优解。但我们暂时无法知道。所以，我们每一步都尝试每一个面额。这非常有利于递归，可以这样写：

def dp_make_weight(egg_weights, target_weight):

    least_taken = float("inf")

    if target_weight == 0:

        return 0

    elif target_weight > 0:

        for weight in egg_weights:

            sub_result = dp_make_weight(egg_weights, target_weight - weight)

            least_taken = min(least_taken, sub_result)

    return least_taken + 1

if __name__ == "__main__":

    print(dp_make_weight((1, 6, 9), 14))

对于每个调用，我们有 3 种可能性：

1. 基本情况target_weight < 0：返回一些东西以表明不可能有解决方案（为了方便起见，我使用了无穷大）。

2. 基本案例target_weight == 0：我们找到了一个候选解决方案。返回 0 表示此处未采取任何步骤，并为调用者提供一个要递增的基值。

3. 递归案例target_weight > 0：尝试egg_weight通过从总数中减去每个可用的值并递归地探索根植于新状态的路径。在探索了当前状态的所有可能结果之后，选择用最少的步骤达到目标的结果。加 1 计数当前步骤的取蛋并返回。

到目前为止，我们已经看到贪婪的解决方案是不正确的以及如何修复它，但还没有激发动态编程或记忆。DP和memoization是纯粹的优化概念，所以你可以在找到正确的解决方案并需要加速之后添加它们。上述解决方案的时间复杂度是指数级的：对于每个调用，我们都必须产生len(egg_weights)递归调用。

有很多资源可以解释 DP 和记忆化，我相信你的课程涵盖了它，但简而言之，我们上面显示的递归解决方案通过采用不同的递归路径一遍又一遍地重新计算相同的结果，最终导致给出相同的值为target_weight. 如果我们保留一份备忘录（字典），将每次调用的结果存储在内存中，那么每当我们再次遇到调用时，我们都可以查找它的结果，而不是从头开始重新计算它。

def dp_make_weight(egg_weights, target_weight, memo={}):

    least_taken = float("inf")

    if target_weight == 0:

        return 0

    elif target_weight in memo:

        return memo[target_weight]

    elif target_weight > 0:

        for weight in egg_weights:

            sub_result = dp_make_weight(egg_weights, target_weight - weight)

            least_taken = min(least_taken, sub_result)

    memo[target_weight] = least_taken + 1

    return least_taken + 1

if __name__ == "__main__":

    print(dp_make_weight((1, 6, 9, 12, 13, 15), 724)) # => 49

由于我们使用的是 Python，因此“Pythonic”的做法可能是装饰函数。事实上，有一个内置的 memoizer 叫做lru_cache，所以回到我们原来的函数没有任何 memoization，我们可以用两行代码添加 memoization（缓存）：

from functools import lru_cache

@lru_cache

def dp_make_weight(egg_weights, target_weight):

    # ... same code as the top example ...

使用装饰器进行记忆的缺点是调用堆栈的大小与包装器的大小成正比，因此它会增加爆栈的可能性。这是迭代编写 DP 算法的一个动机，自下而上（即，从解决方案基本案例开始，建立这些小解决方案的表格，直到您能够构建全局解决方案），这可能是一个很好的练习如果您正在寻找另一个角度，这个问题。