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

Question

我正在 OpenCourseWare (https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/assignments/) 上学习 MIT6.0002，但我对问题集 1 的 B 部分感到困惑。该问题作为背包问题的一个版本呈现，陈述如下:

[The Aucks have found a colony of geese that lay golden eggs of various weights] They want to carry as few eggs as possible on their trip as they don’t have a lot of space on their ships. They have taken detailed notes on the weights of all the eggs that geese can lay in a given flock and how much weight their ships can hold. Implement a dynamic programming algorithm to find the minimum number of eggs needed to make a given weight for a certain ship in dp_make_weight. The result should be an integer representing the minimum number of eggs from the given flock of geese needed to make the given weight. Your algorithm does not need to return what the weight of the eggs are, just the minimum number of eggs. Assumptions: -All the eggs weights are unique between different geese, but a given goose will always lay the same size egg - The Aucks can wait around for the geese to lay as many eggs as they need [ie there is an infinite supply of each size of egg]. -There are always eggs of size 1 available

问题还指出解决方案必须使用动态规划。我写了一个解决方案(用 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()

Answer 1

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

这道题的情况和经典DP题相似coin change在给定目标值的情况下，我们希望找到最少数量的不同值(value)的硬币来进行找零。某些国家/地区可用的面额，例如美国(使用面值为 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 和 memoization我相信你的类(class)涵盖了它，但简而言之，我们上面显示的递归解决方案通过采用不同的递归路径一遍又一遍地重新计算相同的结果，最终导致为 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 算法的动机之一(即，从解决方案基本案例开始，构建这些小解决方案的表格，直到您能够构建全局解决方案)，这可能是一个很好的练习这个问题，如果你正在寻找另一个角度。