Я пытаюсь получить список с минимальным количеством значений, который дает целевую сумму. Если значение не найдено, нам нужно вернуть None. Сначала я пытался обойтись без переменной memo, в которой хранятся промежуточные результаты, чтобы уменьшить временную сложность. Я получил список со значениями [4,4]
, что правильно, но после добавления памятки я получаю список со значениями [4, 1, 4]
, что неверно. Я новичок в Python. Кто-нибудь может указать на ошибку?
def bestSum(targetSum,numbers,memo={}):
if targetSum in memo.keys():
return memo[targetSum]
if targetSum == 0:
return []
if targetSum<0:
return None
myShortestCombination = None
for num in numbers:
remainder = targetSum - num
reamainderCombination = bestSum(remainder,numbers,memo)
if reamainderCombination != None:
reamainderCombination.append(num)
combination = reamainderCombination
if (myShortestCombination == None) or (len(combination) < len(myShortestCombination)):
myShortestCombination = combination
memo[targetSum] = myShortestCombination
return myShortestCombination
print(bestSum(8,[1,4,5],memo={}))
print(bestSum(100,[1,2,5,25],memo={}))
Отвечает ли это на ваш вопрос? Я пытался решить проблему с наилучшей суммой в Python, но не могу понять, в чем проблема.