給定一個數字串列，找到第一個加起來達到一定總和的數字組合。
例子：
給定串列：[1, 2, 3, 4, 5] 給定總和：5 回應：[1, 4] 回應也可以是 [2, 3]，沒關系。重要的是我們從給定的串列中得到一個數字的組合，這些數字加起來盡可能快地達到給定的總和。
我嘗試在 python 中執行此itertools.combinations操作，但需要的時間太長：
from typing import List
import itertools
def test(target_sum, numbers):
for i in range(len(numbers), 0, -1):
for seq in itertools.combinations(numbers, i):
if(sum(seq) == target_sum):
return seq
if __name__ == "__main__":
target_sum: int = 616
numbers: List[int] = [16, 96, 16, 32, 16, 4, 4, 32, 32, 10, 16, 8, 32, 8, 4, 16, 8, 8, 8, 16, 8, 8, 8, 16, 8, 16, 16, 4, 8, 8, 16, 12, 16, 16, 8, 16, 8, 8, 8, 8, 4, 32, 16, 8, 32, 16, 8, 8, 8, 8, 16, 32, 8, 32, 8, 8, 16, 24, 32, 8]
print(test(target_sum, numbers))
uj5u.com熱心網友回復：
def subsum(tsum, numbers):
a = [0]*(tsum 1)
a[0] = -1
for x in numbers:
for i in range(tsum, x-1,-1): #reverse to avoid reusing the same item
if a[i-x] and a[i] == 0: #we can form sum i with item x and existing sum i-x
a[i] = x #remember the last item for given sum
res = []
idx = tsum
while idx:
res.append(a[idx])
idx -= a[idx]
return res
print(subsum(21, [2,3,5,7,11]))
>>>[11, 7, 3]
當最后一個單元格不為零時，組合確實存在，我們可以檢索專案。
復雜性是O(target_sum*len(numbers))
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532363.html
標籤：算法和组合动态规划排列
上一篇：C -撰寫排序函式的問題