时间戳

首页 > 解决方案 > 找到解决方案时退出递归调用树

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

问题描述

我有这个问题，给定一组数字 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]

等等

当我找到第一个答案时，我怎么能退出这个算法？

标签： pythonalgorithm

解决方案

由于您没有使用返回值：

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, [])

推荐阅读