如何将整数列表分成两组整数，其总和差异最小？

假设您只有两行，如图所示，您的问题可以被框定为分区问题的优化变体 - 获取多组整数（在您的情况下为宽度）并将它们划分为两个子集的问题，其中它们的元素总和（组合宽度）的差异最小化。

有一些近似算法，也有一些精确的算法。问题是 NP 困难的，但考虑到您上面显示的元素数量，问题大小应该足够小，不会成为问题。如果你想要一个非常精确/精确的解决方案，或者想要一个随时算法，我建议你使用完整的Karmarkar-Karp算法。

在您的特定情况下，我可能会选择伪多项式时间数划分算法。你没有很多元素，所以这部分不会导致任何内存问题，只有数字的大小（元素宽度）可能会有问题。如果数字太大，我会将它们四舍五入到最接近的 X 像素，然后将所有宽度除以 X，以获得更小的数字（以牺牲一定的准确性为代价，除非您实际调整组件大小以真正成为 X 像素宽度的倍数）。

最后一件事：如果你想在元素之间填充，你也需要在宽度中包含它。

这是一个使用动态编程的简单解决方案。

def split (lengths):
    path = {0: [-1]}
    target = sum(lengths) // 2
    for i in range(len(lengths)):
        next_path = path.copy()
        value = lengths[i]
        for prev_value, prev_path in path.items():
            next_value = value + prev_value
            if next_value <= target and next_value not in next_path:
                next_path[value + prev_value] = [i, prev_path]
        path = next_path

    group_a = []
    group_b = []
    path_data = path[max(path.keys())]
    for i in range(len(lengths) - 1, -1, -1):
        if i == path_data[0]:
            group_a.append(lengths[i])
            path_data = path_data[1]
        else:
            group_b.append(lengths[i])

    return (list(reversed(group_a)), list(reversed(group_b)), sum(group_b) - sum(group_a))


lengths = [240, 255, 270, 240, 220, 230, 420, 470]
print(split(lengths))

当我发布这个问题时，我没有多想，我绝对没有尽力而为。我只是尝试了一种蹩脚的方法来问这个问题，因为我知道在不到 2 次^{n-1 次}迭代中很难找到 n 个元素的确切解决方案。

但现在我又试了一次，找到了两个更好的解决方案。一种是我发现的获得精确解决方案的最有效方法，另一种是找到良好近似值的非常有效的方法。

                                       1

                                    1    1

                                  1    2    1

                               1    3    3    1

                             1    4    6    4    1

                          1    5    10   10   5    1

                        1    6    15   20   15   6    1

                     1    7    21   35   35   21   7    1

                   1    8    28   56   70   56   28   8    1

                1    9    36   84  126  126   84   36   9    1

              1    10   45  120  210  252  210  120   45   10   1

           1    11   55  165  330  462  462  330  165   55   11   1

         1    12   66  220  495  792  924  792  495  220   66   12   1

      1    13   78  286  715  1287 1716 1716 1287 715  286   78   13   1

    1    14   91  364  1001 2002 3003 3432 3003 2002 1001 364   91   14   1

 1    15  105  455  1365 3003 5005 6435 6435 5005 3003 1365 455  105   15   1

以上是帕斯卡三角形。每个数字表示从 r 的总体中选择 c 元素而不重复的方法总数，其中 c 是数字所在列的索引，r 是数字所在的行索引，索引从 0 开始。

从 n 个元素中进行选择的总可能方式是 2ⁿ。

现在正如你所看到的，三角形是对称的，组是互斥的，这意味着如果你选择了一个元素，你会自动知道其他n个元素——一个没有选择的元素。因此，我只需要生成长度为 i 的样本的所有可能组合，其中 1 <= i <= n // 2，然后找到总和差最小的对。

此方法需要帕斯卡三角形迭代的第 n 行的一半才能找到 n 个元素的解。

该系列是：

In [2734]: [sum(row[:i // 2 + i % 2]) for i, row in enumerate(pt.data, start=1)]
Out[2734]: [1, 1, 3, 4, 11, 16, 42, 64, 163, 256, 638, 1024, 2510, 4096, 9908, 16384]

我没有仔细看过它，但这个系列或多或少是 2^{n - 1}。

另一种方法要简单得多，它在 O（log n + n） 时间内找到一个解决方案，但解决方案并不是最好的。第一步是以相反的顺序对元素进行排序，以便较大的数字列在较小的数字之前。

这是为了最大程度地减少后面数字的影响，因此即使路径不是最佳路径，它们也不会对两个列表之间的差异产生太大影响。

下一部分很简单，做两个空列表。然后，对于每个数字，计算一个列表的总和加上另一个列表的数字和之和之间的绝对差。并将数字附加到列表中，以产生最小的差异。

此解决方案在每个交汇点做出最优决策，但未找到全局最优。

from itertools import chain, combinations

def even_bisect(s):
    s = list(s)
    total = sum(s)
    choices = chain.from_iterable(combinations(s, i) for i in range(1, len(s) // 2 + 1))
    triples = []
    for choice in choices:
        other = s.copy()
        for e in choice:
            other.remove(e)

        triples.append((choice, tuple(other), abs(2 * sum(choice) - total)))

    return min(triples, key=lambda x: x[2])


def even_partition(numbers):
    assert len(numbers) >= 2
    numbers = sorted(numbers, reverse=True)
    l1 = []
    l2 = []
    s1 = 0
    s2 = 0
    for n in numbers:
        d1 = abs(s1 + n - s2)
        d2 = abs(s2 + n - s1)
        if d1 <= d2:
            l1.append(n)
            s1 += n
        else:
            l2.append(n)
            s2 += n

    return l1, l2

In [2738]: lengths = [240, 255, 270, 240, 220, 230, 420, 470]

In [2739]: %timeit even_partition(lengths)
4.68 µs ± 100 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [2740]: %timeit even_bisect(lengths)
167 µs ± 1.72 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [2741]: even_bisect(lengths)
Out[2741]: ((240, 270, 240, 420), (255, 220, 230, 470), 5)

In [2742]: a, b = even_partition(lengths)

In [2743]: a, b, abs(sum(a) - sum(b))
Out[2743]: ([470, 255, 240, 220], [420, 270, 240, 230], 25)