如何相似地分配多个数字的总和？

Question

有没有什么方法可以让分配的结果更相似，像下面这种方法？我也想知道如何从多个列表中进行分配。这个列表最多只能包含五个数字。

intList = []
for i in range(10):
    intList.append(random.randint(10,200))


listX = []
listY = []

intList.sort(reverse=True)

for i in range(len(intList)):
    if sum(listX) >= sum(listY):
        if len(listY) != 5:
            listY.append(intList[i])
        else:
            listX.append(intList[i])
    else:
        if len(listX) != 5:
            listX.append(intList[i])
        else:
            listY.append(intList[i])

print(f"listx = {listX} \nlisty = {listY}\n sum x = {sum(listX)}, y = {sum(listY)}")

Answer 1

你的解决方案有一个反例：

[8, 7, 5, 4, 4, 1]

你这样加起来会得到这些子集：

[8, 4, 4], [7, 5, 1]: difference of sums = 3

而最优解是：

[8, 5, 4], [7, 4, 1]: difference of sums = 1

所以，要解决这个问题，你需要穷举所有组合，也就是从n个元素中选择n/2个元素，找到差值最小的那一个。这里有一段示例代码：

comb = []
def getcomb(l, ind, k):
    if len(comb) == k:
        return [comb[:]]
    if ind == len(l):
        return []
    ret = getcomb(l, ind+1, k)
    comb.append(l[ind])
    ret += getcomb(l, ind+1, k)
    comb.pop()
    return ret

def get_best_split(l):
    lsm = sum(l)
    best = lsm
    a = []
    for i in getcomb(l, 0, len(l)//2):
        sm = sum(i)
        if abs(sm - (lsm - sm)) < best:
            best = abs(sm - (lsm - sm))
            a = i

    b = [x for x in l if x not in a]
    return best, a, b

print(get_best_split([8, 7, 5, 4, 4, 1])) 
# outputs (1, [7, 4, 4], [8, 5, 1])

编辑：

如果你不在乎子集本身，那么你可以直接生成所有可能的和：

def getcomb(l, ind, k, val):
    if k == 0:
        return [val]
    if ind == len(l):
        return []
    return getcomb(l, ind+1, k, val) + getcomb(l, ind+1, k-1, val + l[ind]) 

def get_best_split(l):
    l = sorted(l, reverse=True)
    best = 1000000
    for i in getcomb(l, 0, len(l)//2, 0):
        best = min(best, abs(i - (sum(l) - i)))
    return best

编辑 2： 另一个有趣的尝试是修改版的背包问题解决方案，你可以记录每个值能由多少个元素组合而成。这样复杂度会是N^2 * sum(L)，这在某些情况下可能比从N中选择N/2要好，具体取决于你列表中元素的平均值有多大：

def get_best_split_knapsack(l):
    sm = sum(l)
    dp = [[-1, set()] for _ in range(sm+1)]
    dp[0][0] = 1
    dp[0][1].add(0)

    best = sm 

    for i in l:
        for j in range(sm//2, i-1, -1):
            if dp[j-i][0] == 1:
                dp[j][0] = 1
                dp[j][1].update(k+1 for k in dp[j-i][1])
        
        for j in range(max(0,int(sm//2-best)), min(int(sm//2+best)+1, sm)):
            if dp[j][0] == 1 and len(l)//2 in dp[j][1]:
                best = min(best, abs(sm/2 - j))
        
    return int(2*best)

Answer 2

你应该先把整数列表按从大到小的顺序排列，然后遍历这个列表，把每个数字加到当前和较小的那个列表里，像下面这样：

import random

intList = []
for i in range(10):
    intList.append(random.randint(10, 200))

listX = []
listY = []

intList.sort(reverse=True)

sumX = 0
sumY = 0

for num in intList:
    if sumX <= sumY:
        listX.append(num)
        sumX += num
    else:
        listY.append(num)
        sumY += num

print(f"listx = {listX} \nlisty = {listY}\n sum x = {sumX}, y = {sumY}")

编辑

为了确保两个列表都有正好5个元素，并且保持长度平衡，你可以调整算法，根据列表的长度来分配数字。如果某个列表的元素少于5个，就优先往这个列表里添加数字，直到它达到5个元素。

试试这个：

import random

intList = []
listX = []
listY = []

for i in range(10):
    num = random.randint(0, 5)
    intList.append(num)

intList.sort(reverse=True)

sumX = 0
sumY = 0

for num in intList:
    if len(listX) < 5:
        listX.append(num)
        sumX += num
    elif len(listY) < 5:
        listY.append(num)
        sumY += num
    elif sumX <= sumY:
        listX.append(num)
        sumX += num
    else:
        listY.append(num)
        sumY += num

print(f"listx = {listX} \nlisty = {listY}\n sum x = {sumX}, y = {sumY}")