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

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 部分感到困惑。该问题作为背包问题的一个版本提出，表述如下：

\n

\n

[奥克斯发现了一群鹅，它们产下不同重量的金蛋]他们希望在旅途中携带尽可能少的蛋，因为他们的船上\xe2\x80\x99没有足够的空间。他们详细记录了给定鹅群中鹅可以产下的所有鸡蛋的重量，以及它们的船可以承载的重量。\n实现动态规划算法来查找\n达到给定重量所需的最小鸡蛋数量对于 dp_make_weight 中的某艘船。结果应该是一个整数，代表给定鹅群达到给定重量所需的最小鸡蛋数量。您的算法不需要返回鸡蛋的重量，只需返回\n鸡蛋的最小数量。

\n

假设：

\n

\n
• 不同鹅之间的所有鸡蛋重量都是不同的，但同一只鹅总是会产下相同大小的鸡蛋
\n
• 雄鸭可以等待鹅产下所需数量的鸡蛋（即每种尺寸的鸡蛋都有无限的供应）。
\n
• 总是有 1 号鸡蛋可用
\n

\n

\n

该问题还指出该解决方案必须使用动态规划。我写了一个解决方案（用Python），我认为它找到了最佳解决方案，但它没有使用动态编程，而且我无法理解动态编程如何适用。也有人建议解决方案应该使用递归。

\n

任何人都可以向我解释在这种情况下使用记忆化的优点是什么，以及通过实现递归解决方案我会得到什么？\n（如果我的问题太模糊或者解决方案对于文字来说太明显，我深表歉意；我\'我是编程和这个网站的相对初学者）。

\n

我的代码：

\n

#================================\n# Part B: Golden Eggs\n#================================\n\n# Problem 1\ndef dp_make_weight(egg_weights, target_weight, memo = {}):\n    """\n    Find number of eggs to bring back, using the smallest number of eggs. Assumes there is\n    an infinite supply of eggs of each weight, and there is always a egg of value 1.\n    \n    Parameters:\n    egg_weights - tuple of integers, available egg weights sorted from smallest to largest value (1 = d1 < d2 < ... < dk)\n    target_weight - int, amount of weight we want to find eggs to fit\n    memo - dictionary, OPTIONAL parameter for memoization (you may not need to use this parameter depending on your implementation)\n    \n    Returns: int, smallest number of eggs needed to make target weight\n    """\n    egg_weights = sorted(egg_weights, reverse=True) \n    eggs = 0\n    while target_weight != 0:\n        while egg_weights[0] <= target_weight:\n            target_weight -= egg_weights[0]\n            eggs += 1\n        del egg_weights[0]\n    return eggs\n\n\n# EXAMPLE TESTING CODE, feel free to add more if you\'d like\nif __name__ == \'__main__\':\n    egg_weights = (1, 5, 10, 25)\n    n = 99\n    print("Egg weights = (1, 5, 10, 25)")\n    print("n = 99")\n    print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")\n    print("Actual output:", dp_make_weight(egg_weights, n))\n    print()\n

\n

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=None):
    memo = {} if memo is None else 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,
                memo
            )
            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”方式可能是修饰函数。事实上，有一个名为 的内置记忆器cache，所以回到我们原来没有任何记忆化的函数，我们可以用两行代码添加记忆化（缓存）：

from functools import cache

@cache
def dp_make_weight(egg_weights, target_weight):
    # ... same code as the top example ...

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