如何类似地分配几个数的和？

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

您应该按降序对整数列表进行排序，然后迭代它，将每个数字添加到当前总和较小的列表中，如下所示：

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 = [0, 0, 0, 0, 0, 1, 2, 3, 4, 5]
listX = []
listY = []

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

Answer 2

您的解决方案的一个反例是：

[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 select Floor(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
    for i in getcomb(l, 0, len(l)//2):
        sm = sum(i)
        best = min(best, abs(sm - (lsm - sm)))
    return best

print(get_best_split([8, 7, 5, 4, 4, 1])) # outputs 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