Это выглядит как классическая проблема динамического программирования (также указывается другими ответами, в которых упоминается ее сходство с задачами 0-1 по ранцу и сумме подмножества).Все сводится к одному простому выбору: для каждого элемента в списке, используем ли мы его в нашей сумме или нет.Мы можем написать простую рекурсивную функцию для вычисления ответа:
f(index,target_sum)=
0 if target_sum<=0 (i.e. we don't need to add anymore)
infinity if target_sum>0 and index is past the length of n (i.e. we have run out of numbers to add)
min( f(index+1,target_sum), f(index+1,target_sum-n[index])+n[index] ) otherwise (i.e. we explore two choices - 1. take the current number 2. skip over the current number and take their minimum)
Так как эта функция имеет перекрывающиеся подзадачи (она снова и снова исследует одни и те же подзадачи), рекомендуется запомнитьфункция с кешем для хранения значений, которые уже были вычислены ранее.
Вот код на Python:
#! /usr/bin/env python
INF=10**9 # a large enough number of your choice
def min_sum(numbers,index,M, cache):
if M<=0: # we have reached or gone past our target, no need to add any more
return 0
elif len(numbers)==index: # we have run out of numbers, solution not possible
return INF
elif (index,M) in cache: # have been here before, just return the value we found earlier
return cache[(index,M)]
else:
answer=min(
min_sum(numbers,index+1,M,cache), # skip over this value
min_sum(numbers,index+1,M-numbers[index],cache)+numbers[index] # use this value
)
cache[(index,M)]=answer # store the answer so we can reuse it if needed
return answer
if __name__=='__main__':
data=[10,6,3,100]
M=11
print min_sum(data,0,M,{})
Это решение возвращает только минимальную сумму, а не фактические элементы, использованные для ее создания,Вы можете легко расширить идею, чтобы добавить это к вашему решению.