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) 
>>>