问题分区问题

我有一组非唯一的数字，并希望将这些数字分成 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 }

2679

2017-07-12 18:50

起源

因此，无论“set”中的顺序如何，您都要对它们进行分区？ - svick

第一步 - 重新订购设置，第二步 - 执行工作分区 - Randy

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

@Avinash，你的意思是“差不多”？具体要求是什么？你需要找到最好的解决方案吗？ - svick

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

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

在你的情况下 {10, 20, 90, 100, 200}，排序后你得到 {200, 100, 90, 20, 10}。该算法将逐步执行如下操作：

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

这恰好是最佳解决方案。

2017-07-12 19:36

您的第2步是为了澄清，因为第3步包含它。做得好 - Luis Siquot

伟大的解决方案..这是已知的算法或你的。 - Anirudha

是的，非常简单。 - Ivan Voroshilin

鉴于这一点 {3, 3, 2, 2, 2} 同 K=2，这个算法将其分成 {3,2,2}， {3,2} 而最佳解决方案是 {3,3}，{2,2,2}。 - Matt

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

我认为你几乎唯一的选择是使用蛮力，可能还有一些优化（比如修改后的版本）子多项式问题的伪多项式解对于 K = 2）对于简单的情况。也许有更好的算法，但不是更好。

从阅读维基百科的文章分区问题和 3分区问题，我得到你的问题是一般化和稍微修改这些问题的版本，这是NP完整的。

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

2017-07-12 19:44

动态编程在这里很有用，并且比蛮力更好。不幸的是，我不太清楚写一个答案。 - Aryaman

如果你有它一般工作，你只是寻找确定性行为，无论顺序如何，只需先排序集。忽略顺序的所有集合在排序后将是完全相同的序列。

当然它可能会夸大你的运行时复杂性，但我没有看到防止这是一个要求。

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

2017-07-12 19:15

用失败案例更新了问题。 - Avinash

LeetCoder工作过关于Steven Skiena提供的相同问题定义（和解决方案）。唯一的问题是他在C ++中讲话，所以它变得更容易掌握。

2018-04-12 07:51

问题 分区问题