分区问题 [英] The Partition problem

问题描述

我已经设置了非唯一的编号，并希望这些数字分成 K 的分区，这样的数字在每个分区总和几乎相等。 假设我有以下设置。

I have set of non-unique numbers and would like to partition those numbers into K partitions such that sum of numbers in each partition is almost equal . Assume I have following set.

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

使用<一个href="http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM#SECTION02312000000000000000">Linear分区算法我获得以下分区时 K = 3

Using Linear partition algorithm I get following partitions when K = 3

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

这是预期的，但由于这是线性划分算法，输入设定的顺序将改变分区也发生任何变化，这是我想避免的。

Which is expected, but since this is linear partitioning algorithm , any change in the order of the input set will change the partitions also, which I want to avoid.

有每个分区元素之和的差应最小。在每个分区上面的例子总和为 15 ， 13 ， 17

Difference of Sum of elements for each partition should be minimized. In above example Sum of each partitions is 15 , 13, 17

有关下列输入这是行不通的。

for following input it does not work.

{10, 20, 90, 100, 200}

线性分割算法给了我以下

Linear partition algorithm gives me following

{ 10  20  90  100 }
{ 200 }

不过，正确的答案应该是

But correct answer should be

{10，200}  {20，90，100}

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

推荐答案

下面是一个快速贪婪的解决方案（接近最优的大多数情况下）：

Here is a fast greedy solution (near-optimal for most cases):

1. 降序排列
元素
2. 在第一个 K 元素，并把它们分成不同的组
3. 在接下来的 NK 元素，把它们设定的最低金额

1. Sort the elements in descending order
2. Take the first K elements and put them into different sets
3. For the next N-K elements, put them in the set with the lowest sum

在你的情况与 {10，20，90，100，200} ，整理你得到 {200，100，90，20后，10} 。如下算法将逐步完成：

In your case with {10, 20, 90, 100, 200}, after sorting you get {200, 100, 90, 20, 10}. The algorithm will step through as follows:

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

这恰好是最佳的解决方案。

which happens to be the optimal solution.

这篇关于分区问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！