使用动态编程来解决背包问题的版本

问题描述 投票:2回答:1

我正在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部分。该问题以背包问题的形式表示,如下所示:

[[Aucks发现了一群鹅,它们会产下各种重量的金蛋]他们希望在旅行中尽可能少地携带鸡蛋,因为它们没有足够的空间在他们的船上。他们已经详细记录了鹅可以产下的所有鸡蛋的重量在给定的羊群中,它们的船能承受多少重量。实施动态编程算法以查找所需的最小卵数在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()

我正在OpenCourseWare上通过MIT6.0002(https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data -science-fall-2016 / ...

python recursion dynamic-programming
1个回答
1
投票

这里的问题是典型的DP情况,其中贪婪有时]可以提供最佳解决方案,但有时却不能。

© www.soinside.com 2019 - 2024. All rights reserved.