我试图在 Python 中解决最佳总和问题,但我无法弄清楚问题,请提出问题 [英] I tried to solve Best Sum problem in Python but I am not able to figure out the issue, please suggest what is wrong
问题描述
该函数应返回一个数组,其中包含加起来正好等于目标总和的最短数字组合.如果有两种(或更多)可能性,则返回其中任何一种.
The function should return an array containing the shortest combination of numbers that add up to exactly the target sum. If there are two (or more) possibilities, then return any one of them.
def bestSum(targetSum, numbers, memo = {}):
if targetSum in memo: return memo[targetSum]
if targetSum == 0: return []
if targetSum < 0: return None
shortestCombination = None
for num in numbers:
remainder = targetSum - num
remainderCombination = bestSum(remainder, numbers, memo)
if remainderCombination is not None:
remainderCombination.append(num)
if shortestCombination is None or len(remainderCombination) < len(shortestCombination):
shortestCombination = remainderCombination
memo[targetSum] = shortestCombination
return memo[targetSum]
输入调用:bestSum(4, [2,1])
输出:[2, 2, 1]
预期输出:[2,2]
推荐答案
所以解决方案很简单,但当时我没有注意到.我们应该使用 shortestCombination = resumeCombination.copy()
代替像 shortestCombination = ReminderCombination
那样复制列表,这样 shortestCombination 和 RemallCombination 就不会指向内存中的同一个 List.
So the solution was pretty simple but I didn't notice at that time. Instead of copying the list like shortestCombination = remainderCombination
we should use shortestCombination = remainderCombination.copy()
so that the shortestCombination and remainderCombination don't point to the same List in memory.
这是正确的代码,性能也很好
Here is the correct code with good performance as well
def bestSum(targetSum, numbers, memo = {}):
if targetSum in memo: return memo[targetSum]
if targetSum == 0: return []
if targetSum < 0: return None
shortestCombination = None
for num in numbers:
remainder = targetSum - num
remainderCombination = bestSum(remainder, numbers, memo)
if remainderCombination is not None:
remainderCombination.append(num)
if shortestCombination is None or len(remainderCombination) < len(shortestCombination):
shortestCombination = remainderCombination.copy()
memo[targetSum] = shortestCombination
return shortestCombination
if __name__ == '__main__':
print(bestSum(4, [2, 1])) #Output [2, 2]
print(bestSum(300, [2, 7]))
#Output 2, 2, 2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
# 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]
这篇关于我试图在 Python 中解决最佳总和问题,但我无法弄清楚问题,请提出问题的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!