我试图在 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屋！