时间戳

首页 > 解决方案 > 将列表分成两部分，尽可能等于总和

python - 将列表分成两部分，尽可能等于总和

问题描述

我正试图围绕这整个事情展开我的头脑，但我似乎无法弄清楚。基本上，我有一个整数列表。将这些 int 值加起来等于 15。我想将一个列表分成 2 部分，但同时，使每个列表在总和上尽可能接近。对不起，如果我不解释这个很好。

例子：

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)

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

任何帮助，将不胜感激！

标签： pythonalgorithmsplit

解决方案

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

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)

推荐阅读