Python - 總結大於或等於某個值的數字組合

-1

我最近提出了以下面試問題，以Python回答 - 給定一個數量 - 值對列表，找到最佳組合它們的總和接近並且至少與某個提供的值一樣大。例如，給定：[（1，$ 5），（3，$ 10），（2，$ 15）]，期望值爲36美元，則答案爲[（2，$ 15），（1， $ 10）]或[（1，$ 15），（2，$ 10），（1，$ 5）]。原因是40美元是可以實現的大於或等於36美元的最低總和，而這是實現這一總和的兩種方式。Python - 總結大於或等於某個值的數字組合

我被難倒了。有沒有人有辦法解決嗎？

來源

2017-08-31 iOSBeginner

你可以試試'itertools .combinations' – Wen

查找給定數量 - 數值對的所有組合，然後只取最小值[s] –

的數字是如此之小，你可以蠻力它：

In []: 
notes = [(1, 5), (3, 10), (2, 15)] 
wallet = [n for a, b in notes for n in [b]*a] 
combs = {sum(x): x for i in range(1, len(wallet)) for x in it.combinations(wallet, i)} 

target = 36 
for i in sorted(combs): 
    if i >= target: 
     break 
i, combs[i] 

Out[]: 
(40, (5, 10, 10, 15))

您可以擴展此對所有組合，只需更換與combs字典解析：

combs = {} 
for i in range(1, len(wallet)): 
    for x in it.combinations(wallet, i): 
     combs.setdefault(sum(x), set()).add(x) 

... 
i, combs[i] 

Out[]: 
(40, {(5, 10, 10, 15), (10, 15, 15)})

來源

2017-08-31 02:37:30 AChampion

Python - 總結大於或等於某個值的數字組合

回答

相關問題