分区问题

Question

我有一组非唯一的数字,并希望将这些数字划分为K分区,使得每个分区中的数字总和几乎相等.假设我有以下设置.

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

使用线性分区算法我得到以下分区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

这恰好是最佳解决方案.