algorithm - 分区问题

Question

我有一组非唯一数字，我想将这些数字分成 K 分区，这样每个分区中的数字总和几乎相等。假设我有以下集合。

{1, 2, 3, 4, 5, 6, 7, 8, 9}

使用 Linear partition algorithm当 K = 3

时，我得到以下分区

{ 1  2  3  4  5 }
{ 6  7 }
{ 8  9 }

这是预期的，但由于这是线性分区算法，输入集顺序的任何更改也会更改分区，这是我想避免的。

每个分区的元素总和的差异应最小化。在上面的例子中，每个分区的总和是 15 , 13, 17

对于跟随输入它不起作用。

{10, 20, 90, 100, 200}

线性分区算法给了我以下

{ 10  20  90  100 }
{ 200 }

但正确答案应该是

{ 10, 200 }
{ 20, 90, 100 }

Answer 1

这是一个快速贪婪的解决方案(对于大多数情况来说接近最优):

1. 将元素降序排列
2. 取出前 K 个元素并将它们放入不同的集合中
3. 对于接下来的N-K个元素，将它们放入总和最小的集合中

在您使用 {10, 20, 90, 100, 200} 的情况下，排序后您会得到 {200, 100, 90, 20, 10}。该算法将按如下步骤进行:

Set A   Set B
 200     100
 200     190
 200     210
 210     210

这恰好是最优解。