动态编程脚本的最佳求和方法

Question

我试图学习动态规划的一些基本知识，但我遇到了以下问题：

给定一个整数sum和一个正整数列表numbers作为输入，返回由属于numbers的、总计为sum的最小数量组成的列表

希望这是清楚的，我将给你三个例子：

如果sum = 10和numbers = (2, 3, 5)应该返回[5, 5]； ifsum = 0和numbers = (2, 3, 5)应该返回[]； ifsum = 10和numbers = (3)应该返回False

def bestsum(sum, numbers, memo={}):
    if sum == 0:
        return []
    elif sum < 0:
        return False
    else:
        if sum not in memo:
            shortest_combination = False
            for number in numbers:
                remainder = sum - number
                combination = bestsum(remainder, numbers)
                if combination != False:
                    combination.append(number)
                    if shortest_combination == False or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[sum] = shortest_combination
        return memo[sum]

我没有把memo作为我的bestsum递归调用的输入，因为它与我以前做过的其他动态程序一起工作。但是，即使我添加了它，脚本也无法工作，即使我没有显式地这样做，它也会更新memo。添加copy.copy或实际插入我的memo作为输入没有帮助。也许问题在于，当我调用不同的函数，或者递归调用其他函数时，我仍然怀念变量如何在我的记忆中生存

Answer 1

我对代码库做了一些更改并添加了一些注释，但我保留了大部分注释：

def bestsum(sum, numbers, memo={}):
    if sum == 0:
        return []
    elif sum < 0:
        return False
    else:
        if sum not in memo:
            for number in numbers:
                remainder = sum - number
                shortest_combination = bestsum(remainder, numbers, memo)
                if shortest_combination != False:
                    # Good news! We found a valid path from `sum` to the end
                    if (
                        sum not in memo
                        or len(memo[sum]) > len(shortest_combination) + 1
                    ):
                        # Either there's no entry in memo for `sum` yet
                        # Or we've found a better subpath than the current one
                        currently_best_combination = shortest_combination.copy()
                        currently_best_combination.insert(0, number)
                        memo[sum] = currently_best_combination
            if sum in memo:
                # Return value if we've found a valid path 
                return memo[sum]
            else:
                # Return false if not
                return False
        else:
            # If sum is already in `memo`, it's already the optimal way
            return memo[sum]

numbers = [2, 3, 5]
print(bestsum(10, numbers))
# [5, 5]

numbers = [2, 3, 5]
print(bestsum(0, numbers))
# []

numbers = [3]
print(bestsum(10, numbers))
# False

Answer 2

除了注释中列出的问题（即可变默认参数，使用内置名作为变量名）之外，如果传递memo参数（EDIT：实际上想想看，无论如何都会发生这种情况），您还会遇到浅副本

对所有提到的问题进行最快的修复，只需进行最小的更改，就可以解决这个问题

def bestsum(s, numbers, memo=None):
    if memo is None:
        memo = {}
    if s == 0:
        return []
    elif s < 0:
        return False
    else:
        if s not in memo:
            shortest_combination = False
            for number in numbers:
                remainder = s - number
                combination = bestsum(remainder, numbers, memo)
                if combination != False:
                    combination = combination.copy()
                    combination.append(number)
                    if shortest_combination == False or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[s] = shortest_combination
        return memo[s]

（这并不是说这是最优雅的方式，更像是对代码的直接修复）

至于我会怎么做：

def bestsum(s, numbers):
    sums = {0:[]}
    while(s not in sums and len(sums)>0):
        sums = {k+n:l+[n] for k,l in sums.items() for n in numbers if k+n<=s}
    if(s not in sums):
        return None
    else:
        return sums[s]