python - 找到解决方案后退出递归调用树

Question

我有这个问题，给定一组数字 S 和一个数字 N 找到一些数字 S 的组合，总和为 N 使得解决方案使用最少的数字。即最小化|解决方案|

例如，假设 S = {1000, 500, 250, 100}，A = 900，则解 = {500, 100, 100, 100, 100}

这是我的尝试

numbers = [1000, 500, 250, 100]
amount = 900

def solve(numbers, amount, sum, solution):
    for num in numbers:
        if sum + num <= amount:
            if sum + num == amount:
                print(solution + [num])
                return
            solve(numbers, amount, sum + num, solution + [num])

solve(numbers, amount, 0, [])

而且有效!有点，我得到了正确的答案，它总是我打印的第一个值(因为我确保这组数字是按降序排列的)。但是该算法继续打印所有其他正确答案(这里正确的意思是总而言之不最小化 |Solution|)

[500, 100, 100, 100, 100] [250, 250, 100, 100, 100, 100] [250, 100, 250, 100, 100, 100] [250, 100, 100, 250, 100, 100] [250, 100, 100, 100, 250, 100] [250, 100, 100, 100, 100, 250]

等等

当我找到第一个答案时，如何退出该算法？

Answer 1

因为您没有使用返回值:

numbers = [1000, 500, 250, 100]
amount = 900
def solve(numbers, amount, sum, solution):
    for num in numbers:
        if sum + num <= amount:
            if sum + num == amount:
                print(solution + [num])
                return True
            if solve(numbers, amount, sum + num, solution + [num]):
                return True
     return False

solve(numbers, amount, 0, [])