Python - 如何總結一列數字的所有組合以達到目標。數量的使用是可選

Question

我有一個數字

lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68] 

，我想以各種方式來總結，以試圖達到8276.目標數量我還需要看看是否扔掉的列表美分或舍入有助於實現目標。請注意，使用數字是可選的。

我試圖

from itertools import combinations 
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68] 
for i in xrange(1, len(lis) + 1): #xrange will return the values 1,2,3,4 in this loop 
    if sum(list(combinations(lis, i))) == 8276: 
     print list(combinations(lis, i)) 

，但是這給了我

TypeError: unsupported operand type(s) for +: 'int' and 'tuple' 

，我不知道爲什麼或如何解決。

Answer 1

既然你提到：

我還需要看看是否扔掉美分或倒圓有助於達到目標。

..下面的代碼將顯示最接近的n-組合，以及它們顯示的目標數量的絕對差值。

工程上都python3和python2

from itertools import combinations 
# set the number of closest combinations to show, the targeted number and the list 
show = 5 
target = 8276 
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68] 

diffs = [] 
for n in range(1, len(lis)+1): 
    numbers = combinations(lis, n) 
    # list the combinations and their absolute difference to target 
    for combi in numbers: 
     diffs.append([combi, abs(target - sum(combi))]) 

diffs.sort(key=lambda x: x[1]) 

for item in diffs[:show]: 
    print(item[0], round(item[1],10)) 

輸出將顯示的頂Ñ最接近組合（組合/絕對差與目標號碼）：

(5084, 3298.85) 106.85 
(10, 5084, 3298.85) 116.85 
(5084, 156.43, 3298.85) 263.28 
(10, 5084, 156.43, 3298.85) 273.28 
(5084, 381.3, 3298.85) 488.15 

這表明最近你可以得到是(5084, 3298.85)，顯示差異106.85。

---

注

見BTW Note on floating point calculation：

---

編輯

對於它的運動，上面的腳本的精簡版：

from itertools import combinations 
# set the number of closest combinations to show, the targeted number and the list 
show = 5 
target = 8276 
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68] 

diffs = [item for sublist in [[ 
    [combi, abs(target - sum(combi))] for combi in combinations(lis, n) 
    ] for n in range(1, len(lis)+1)] for item in sublist] 

diffs.sort(key=lambda x: x[1]) 
[print(item[0], round(item[1],10)) for item in diffs[:show]] 

Answer 2

您試圖將給定長度的所有組合總和，而不是計算單個組合的總和。相反，你應該在組合循環，並檢查每一個總和：

from itertools import combinations 
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68] 
for i in xrange(1, len(lis) + 1): 
    for comb in combinations(lis, i): 
     if sum(comb) == 8276: 
      print comb 

的原因特定的錯誤是sum採用可選參數start這是默認值。如果未提供參數，則默認爲0。基本上你原來的代碼試圖做到以下幾點：

>>> sum([(1,), (2,)]) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: unsupported operand type(s) for +: 'int' and 'tuple' 

Answer 3

這裏是一個解決方案，如果你想考慮的情況下，你可以扔掉美分，或者你可以四捨五入到最接近的整數。這個要求把一個簡單的解決方案變成了一個非常複雜的解決方案爲了解釋上述要求，我擴展了每個號碼以包括額外的可能情況。展開的列表顯示了新的名單，以獲得組合：

import math 
import itertools as it 
tolerance = 150 
target_sum = 8392 
found = False 
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68] 

def add_throw_and_round(num): 
    num_list = [num] 
    if int(num) != float(num): 
     num_list.append(math.floor(num)) 
    if round(num) not in num_list: 
     num_list.append(round(num)) 
    return sorted(num_list) 

lis_expanded = map(add_throw_and_round, lis) 
print "Expanded list:\n", lis_expanded, "\n\nTarget sum:\n", target_sum, "\n" 
for n in range(1,len(lis) + 1): # n is number of summands in pick 
    lis_combos = it.combinations(lis_expanded, n) 
    for lis_combo_n in lis_combos: 
     for combo_n in (it.product(*lis_combo_n)): 
      sum_ = sum(combo_n) 
      if sum_ == target_sum: 
       found = True 
       answer = combo_n 
      if sum_ > target_sum - tolerance and sum_ < target_sum + tolerance: 
       print "sum:", sum_, "\tCombination: ", combo_n 
if found: 
    print "\nThere is a match: ", answer 
else: 
    print "\nNo exact match found" 

所以我決定以表明是內部目標總的150，只是爲了看看它工作的所有款項。目前還沒有比賽是總和正好是8276：

>>> 
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py ===== 

Expanded list: 
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]] 

Target sum: 
8276 

sum: 8382.0  Combination: (5084, 3298.0) 
sum: 8382.85 Combination: (5084, 3298.85) 
sum: 8383.0  Combination: (5084, 3299.0) 
sum: 8392.0  Combination: (10, 5084, 3298.0) 
sum: 8392.85 Combination: (10, 5084, 3298.85) 
sum: 8393.0  Combination: (10, 5084, 3299.0) 

No exact match found 
>>> 

注意上面它測試，其中美分被拋出，並四捨五入的情況。 只是爲了測試當目標總和是否匹配時它會報告匹配，我嘗試了target_sum = 8392，因爲輸出顯示一個組合應該匹配它。所以這裏是這種情況下的輸出：

>>> 
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py ===== 
Expanded list: 
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]] 

Target sum: 
8392 

sum: 8382.0  Combination: (5084, 3298.0) 
sum: 8382.85 Combination: (5084, 3298.85) 
sum: 8383.0  Combination: (5084, 3299.0) 
sum: 8392.0  Combination: (10, 5084, 3298.0) 
sum: 8392.85 Combination: (10, 5084, 3298.85) 
sum: 8393.0  Combination: (10, 5084, 3299.0) 
sum: 8538.0  Combination: (5084, 156.0, 3298.0) 
sum: 8538.85 Combination: (5084, 156.0, 3298.85) 
sum: 8539.0  Combination: (5084, 156.0, 3299.0) 
sum: 8538.43 Combination: (5084, 156.43, 3298.0) 
sum: 8539.28 Combination: (5084, 156.43, 3298.85) 
sum: 8539.43 Combination: (5084, 156.43, 3299.0) 

There is a match: (10, 5084, 3298.0) 
>>>