假设我有一个数字 S = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1] 的数组。我想分成三个数组。这些数组中数字的顺序和项目的数量无关紧要。

假设 A1、A2 和 A3 是子数组。我想最小化函数

f(x) = ( SUM(A1) - SUM(S) / 3 )^2 / 3 +
       ( SUM(A2) - SUM(S) / 3 )^2 / 3 +
       ( SUM(A3) - SUM(S) / 3 )^2 / 3

• 我不需要最优解；我只需要足够好的解决方案。
• 我不想要太慢的算法。我可以用一些速度换取更好的结果，但我不能换得太多。
• S 的长度在 10 到 30 左右。

为什么

为什么我需要解决这个问题？我想把盒子很好地排列成三列，这样每列的总高度不会相差太大。

我尝试了什么

我的第一直觉是使用贪婪。结果还不错，但并不能确保最佳解决方案。有没有更好的办法？

s = [6, 2, 1, 7, 4, 3, 9, 5, 3, 1]
s = sorted(s, reverse=True)

a = [[], [], []]
sum_a = [0, 0, 0]

for x in s:
    i = sum_a.index(min(sum_a))
    sum_a[i] += x
    a[i].append(x)

print(a)

最佳答案

正如您所说，您不介意非最佳解决方案，但我会重新使用您的初始功能，并添加一种方法来为您的初始列表 s 找到一个好的开始安排

你的初始函数:

def pigeon_hole(s):
    a = [[], [], []]
    sum_a = [0, 0, 0]
    for x in s:
        i = sum_a.index(min(sum_a))
        sum_a[i] += x
        a[i].append(x)
    return map(sum, a)

这是一种为您的列表找到合理的初始排序的方法，它通过按排序和反向排序顺序创建列表的轮换来工作。一旦列表被归类，通过最小化标准偏差来找到最佳轮换:

def rotate(l):
    l = sorted(l)
    lr = l[::-1]
    rotation = [np.roll(l, i) for i in range(len(l))] + [np.roll(lr, i) for i in range(len(l))]
    blocks = [pigeon_hole(i) for i in rotation]
    return rotation[np.argmin(np.std(blocks, axis=1))]  # the best rotation

import random
print pigeon_hole(rotate([random.randint(0, 20) for i in range(20)]))

# Testing with some random numbers, these are the sums of the three sub lists
>>> [64, 63, 63]

虽然这可以进一步优化，但对于 20 个数字只需 0.0013 秒。使用 a = rotate(range(1, 30))

# This method
a = rotate(range(1, 30))
>>> [[29, 24, 23, 18, 17, 12, 11, 6, 5], [28, 25, 22, 19, 16, 13, 10, 7, 4, 1], [27, 26, 21, 20, 15, 14, 9, 8, 3, 2]]
map(sum, a)
# Sum's to [145, 145, 145] in 0.002s

# Mo Tao's method
>>> [[25, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [29, 26, 20, 19, 18, 17, 16], [28, 27, 24, 23, 22, 21]]
# Sum's to [145, 145, 145] in 1.095s

这种方法似乎在许多情况下也能找到最佳解决方案，尽管这可能不适用于所有情况。使用包含 30 个数字的列表与莫涛的答案测试此实现 500 次，并比较子列表的总和是否相同:

c = 0
for i in range(500):
    r = [random.randint(1, 10) for j in range(30)]
    res = pigeon_hole(rotate(r))
    d, e = sorted(res), sorted(tao(r))  # Comparing this to the optimal solution by Mo Tao
    if all([k == kk] for k, kk in zip(d, e)):
        c += 1
    memory = {}
    best_f = pow(sum(s), 3)
    best_state = None

>>> 500 # (they do)

我想我会在这里提供一个更优化版本的函数更新:

def rotate2(l):
    # Calculate an acceptable minimum stdev of the pigeon holed list
    if sum(l) % 3 == 0:
        std = 0
    else:
        std = np.std([0, 0, 1])

    l = sorted(l, reverse=True)
    best_rotation = None
    best_std = 100

    for i in range(len(l)):
        rotation = np.roll(l, i)
        sd = np.std(pigeon_hole(rotation))

        if sd == std:  
            return rotation  # If a min stdev if found 

        elif sd < best_std:
            best_std = sd
            best_rotation = rotation

    return best_rotation

主要的变化是一旦找到合适的轮换，对良好排序的搜索就会停止。也只搜索反向排序的列表，这似乎不会改变结果。用

print timeit.timeit("rotate2([random.randint(1, 10) for i in range(30)])", "from __main__ import rotate2, random", number=1000) / 1000.

导致大幅加速。在我当前的计算机上，rotate 大约需要 1.84 毫秒，rotate2 大约需要 0.13 毫秒，因此速度提高了 14 倍。为了比较 גלעד ברקן 的实现在我的机器上花费了大约 0.99 毫秒。

关于python - 将列表分成三个列表，使它们的总和彼此接近，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41221874/