将列表分成两部分，尽可能相等

Question

我试图把我的头包裹在整件事上，但我似乎无法弄清楚。基本上，我有一个整数列表。将这些 int 值相加等于 15。我想将列表分成两部分，但同时，使每个列表的总和尽可能接近。对不起，如果我没有解释这个好。

例：

list = [4,1,8,6]

我想实现这样的事情：

list = [[8, 1][6,4]]

将第一个列表相加等于 9，另一个列表等于 10。这对于我想要的东西来说是完美的，因为它们尽可能接近。

我现在拥有的：

my_list = [4,1,8,6]  
total_list_sum = 15
def divide_chunks(l, n): 

# looping till length l 
for i in range(0, len(l), n):  
yield l[i:i + n] 
n = 2
x = list(divide_chunks(my_list, n)) 
print (x) 

但是，这只是将其分为两部分。

任何帮助将不胜感激！

Answer 1

您可以使用递归算法和列表的"蛮力"分区。 从目标差值为零开始，逐渐增加对两个列表之间差值的容忍度：

def sumSplit(left,right=[],difference=0):
sumLeft,sumRight = sum(left),sum(right)
# stop recursion if left is smaller than right
if sumLeft<sumRight or len(left)<len(right): return
# return a solution if sums match the tolerance target
if sumLeft-sumRight == difference:
return left, right, difference
# recurse, brutally attempting to move each item to the right
for i,value in enumerate(left):
solution = sumSplit(left[:i]+left[i+1:],right+[value], difference)
if solution: return solution
if right or difference > 0: return 
# allow for imperfect split (i.e. larger difference) ...
for targetDiff in range(1, sumLeft-min(left)+1):
solution = sumSplit(left, right, targetDiff)
if solution: return solution 

# sumSplit returns the two lists and the difference between their sums
print(sumSplit([4,1,8,6]))     # ([1, 8], [4, 6], 1)
print(sumSplit([5,3,2,2,2,1])) # ([2, 2, 2, 1], [5, 3], 1)
print(sumSplit([1,2,3,4,6]))   # ([1, 3, 4], [2, 6], 0)

Answer 2

使用itertools.combinations(详情请点击此处)。首先，让我们定义一些函数：

def difference(sublist1, sublist2):
return abs(sum(sublist1) - sum(sublist2))
def complement(sublist, my_list):
complement = my_list[:]
for x in sublist:
complement.remove(x)
return complement

该函数difference计算列表之间的"距离"，即两个列表的总和有多相似。complement返回不在sublist中的my_list元素。

最后，您正在寻找什么：

def divide(my_list):
lower_difference = sum(my_list) + 1
for i in range(1, int(len(my_list)/2)+1):
for partition in combinations(my_list, i):
partition = list(partition)
remainder = complement(partition, my_list)
diff = difference(partition, remainder)
if diff < lower_difference:
lower_difference = diff
solution = [partition, remainder]
return solution
test1 = [4,1,8,6]
print(divide(test1)) #[[4, 6], [1, 8]]
test2 = [5,3,2,2,2,1]
print(divide(test2)) #[[5, 3], [2, 2, 2, 1]]

基本上，它尝试对子列表进行所有可能的划分，并返回具有最小"距离"的子列表。

如果你想让它快一点，你可以返回第一个组合，其差值为 0。

Answer 3

我认为您正在寻找的是爬山算法。我不确定这会涵盖所有情况，但至少适用于您的示例。如果我想到一个反例或其他东西，我会更新这个。

让我们称您的数字列表为vals.

vals.sort(reverse=true)
a,b=[],[]
for v in vals:
if sum(a)<sum(b):
a.append(v)
else: 
b.append(v)