将列表分成 2 部分，尽可能等于总和 [英] Splitting list into 2 parts, as equal to sum as possible

问题描述

我正试图围绕这整件事进行思考，但我似乎无法弄清楚.基本上，我有一个整数列表.将这些 int 值相加等于 15.我想将一个列表分成 2 部分，但同时，使每个列表在总和上尽可能彼此接近.对不起，如果我没有解释清楚.

I'm trying to wrap my head around this whole thing and I can't seem to figure it out. Basically, I have a list of ints. Adding up those int values equals 15. I want to split up a list into 2 parts, but at the same time, making each list as close as possible to each other in total sum. Sorry if I'm not explaining this good.

示例:

list = [4,1,8,6]

我想实现这样的目标:

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

将第一个列表加起来等于 9，另一个等于 10.这非常适合我想要的，因为它们尽可能接近.

adding the first list up equals 9, and the other equals 10. That's perfect for what I want as they are as close as possible.

我现在拥有的:

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) 

但是，这只是将其分成两部分.

But, that just splits it up into 2 parts.

任何帮助将不胜感激！

推荐答案

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

You could use a recursive algorithm and "brute force" partitioning of the list. Starting with a target difference of zero and progressively increasing your tolerance to the difference between the two lists:

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)

这篇关于将列表分成 2 部分，尽可能等于总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！