在特定条件下将数字列表分配给N组的算法

Question

假设我有一个数字列表:

2,2,3,4,4

将数字分成N组(这里以3组为例):

A:2,3 sum:5

B:4   sum:4

C:2,4 sum:6

我想要的是最小化总和最高的组(此处为 6)- 总和最小的组(此处为 4)。

有没有人想出一个算法来实现这个？

---

另一个例子:

7,7,8,8,8,9,9,10

结果应该是这样的:

A:7,8,8 sum:23

B:7,8,9 sum:24

C:9,10  sum:19

Answer 1

不幸的是，这个问题是 NP 难的。请参阅 multiprocessor scheduling 的引用资料或 bin packing .如果您对这种方法感兴趣，您也许还能找到一些有用的近似算法。