分区问题

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 }

- Avinash

---

所以您想要对它们进行分区，而不考虑“集合”中的顺序？ - svick

第一步 - 重新排序集合，第二步 - 执行工作分区。 - Randy

@svick，换句话说，当输入和分区数量相同时，无论输入数字如何排列，它始终会给我相同的分区集。 - Avinash

@Avinash，您所说的“几乎相等”是什么意思？具体的要求是什么？您需要找到最佳解决方案吗？ - svick

@svick，我会更新问题。 - Avinash

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

这恰好是最佳解决方案。

- tskuzzy

---

你的第二步是为了澄清，因为第三步已经包含了它。干得好！ - Saic Siquot

这是一个很棒的解决方案..这是已知的算法还是你自己的创意？ - Anirudha

对于给定的集合 {3, 3, 2, 2, 2}，当 K=2 时，该算法将其划分为 {3,2,2}, {3,2}，而最优解是 {3,3},{2,2,2}。 - Matt

我该如何证明这个算法的正确性？我的意思是，如果列表没有排序或按升序排序，那么这个算法将失败。我无法证明这个算法。 - ffff

Answer 2

我认为你唯一的选择就是使用暴力破解，可能会有一些优化（例如对于简单情况，使用修改版的子集和问题的伪多项式解法来处理K = 2）。也许有更好的算法，但不会好到哪里去。

从阅读维基百科上关于划分问题和三分问题的文章中，我了解到你的问题是这些问题的广义和稍作修改的版本，它们都是NP完全问题。

更具体地说，如果你有一个有效的算法来解决你的问题，它也将能够有效地解决上述两个问题，这是不可能的（除非P = NP）。

- svick

---

动态规划可能在这里很有用，而且比暴力算法更好。不幸的是，我不知道足够的知识来写出一个答案。 - Aryaman

Answer 3

如果您已经将其总体上运作，并且只是寻找无论顺序如何都具有确定性行为的解决方案，只需先对集合进行排序。所有在忽略顺序的情况下相同的集合，在排序后将成为完全相同的序列。

当然，这可能会增加您的运行时复杂度，但我没有看到防止这种情况的要求。

所有这些都基于您的评论，即数字的排列确实并不重要。此时，这肯定不同于您链接到的问题，该问题假定分区永远不需要重新排列元素。

- Mark Peters

Answer 4

LeetCoder 已经在 Steven Skiena 提供的相同问题定义（和解决方案）上工作过。唯一的区别是他使用 C++ 进行讲解，因此更容易理解。

- Amol