一种算法,用于将值列表分类为n个组,以便每个组的总和尽可能接近

Question

基本上我有很多值需要分成n个不同的组,以便每组的总和尽可能接近其他组的总和？值列表并不是非常长,所以我可能只是暴力强迫它,但我想知道是否有人知道这样做更有效的方法.谢谢.

Answer 1

如果近似解是足够的,那么将数字降序排序,循环它们并将每个数字分配给具有最小总和的组.

groups = [list() for i in range(NUM_GROUPS)]
for x in sorted(numbers, reverse=True):
    mingroup = groups[0]
    for g in groups:
        if sum(g) < sum(mingroup):
           mingroup = g
    mingroup.append(x)

Answer 2

这个问题被称为“多路分区问题”，并且确实在计算上很困难。谷歌搜索它返回了一篇有趣的论文“Multi-Way Number Paritioning，其中作者提到了启发式建议larsmans并提出了一些更高级的算法。如果上述启发式还不够，您可以查看论文或联系作者，他似乎在做这方面的研究。