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

Question

我是一名有用的助手，可以为您翻译文本。

我正在通过MIT6.0002开放式课程学习（https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/assignments/），我在第一组问题集的B部分遇到了难题。这个问题被描述为背包问题的一个版本，其陈述如下：

[奥克斯发现了一群鹅，它们产下各种重量的金蛋] 他们希望在航行时尽可能少地携带金蛋，因为他们的船只空间有限。他们已经详细记录了鹅群中所有蛋的重量以及他们的船只可以承受多少重量。 实现一个动态规划算法，在 dp_make_weight 中找到制造给定重量所需的最少鸡蛋数。结果应该是一个整数，代表从给定的鹅群中制造给定重量所需的最少鸡蛋数。你的算法不需要返回鸡蛋的重量，只需要返回最少的鸡蛋数量。 假设： - 不同鹅之间的所有蛋的重量都是唯一的，但是同一只鹅总是会产下相同大小的蛋 - 奥克斯可以等待鹅产出他们需要的任意数量的蛋[即每种大小的蛋都有无限供应] - 总是有大小为1的蛋可用

这个问题要求解决方案必须使用动态规划。我写了一个解决方案（用Python），我认为它可以找到最优解，但它没有使用动态规划，我也不明白如何应用动态规划。还有建议说解决方案应该使用递归。

有人能向我解释一下在这种情况下使用记忆化的优势是什么，以及如果我实现一个递归解决方案，我将获得什么好处？ （如果我的问题太模糊或者解决方案对于初学编程和这个网站的人来说太明显，那我很抱歉）。

我的代码:

#================================
# Part B: Golden Eggs
#================================

# Problem 1
def dp_make_weight(egg_weights, target_weight, memo = {}):
    """
    Find number of eggs to bring back, using the smallest number of eggs. Assumes there is
    an infinite supply of eggs of each weight, and there is always a egg of value 1.
    
    Parameters:
    egg_weights - tuple of integers, available egg weights sorted from smallest to largest value (1 = d1 < d2 < ... < dk)
    target_weight - int, amount of weight we want to find eggs to fit
    memo - dictionary, OPTIONAL parameter for memoization (you may not need to use this parameter depending on your implementation)
    
    Returns: int, smallest number of eggs needed to make target weight
    """
    egg_weights = sorted(egg_weights, reverse=True) 
    eggs = 0
    while target_weight != 0:
        while egg_weights[0] <= target_weight:
            target_weight -= egg_weights[0]
            eggs += 1
        del egg_weights[0]
    return eggs


# EXAMPLE TESTING CODE, feel free to add more if you'd like
if __name__ == '__main__':
    egg_weights = (1, 5, 10, 25)
    n = 99
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 99")
    print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

- sam R

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并递归探索根源于新状态的路径来获取每个可用的egg_weight。在探索当前状态的每种可能结果之后，选择达到目标所需的最少步骤。将1添加到计算当前步骤所采取的蛋，并返回。

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

有许多资源可以解释DP和memoization，我相信你的课程已经涵盖了，但简而言之，我们上面展示的递归解决方案通过不同的递归路径重新计算相同的结果，这些路径最终导致为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”的方法是修饰函数。实际上，有一个内置的记忆化器叫做lru_cache，因此回到我们原始的没有任何记忆化的函数，我们可以通过两行代码添加记忆化（缓存）：

from functools import lru_cache

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

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

- ggorlen