分區問題

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 

這恰好是最佳解決方案。

Answer 2

如果您有它在一般的工作和你只是在尋找確定性的行爲不管順序如何，只要先排序。所有屬於同一個無視順序的集合在排序後都是完全相同的順序。

當然，它可能會誇大您的運行時複雜性，但我沒有看到阻止這是需求。

這一切都基於您的評論，數字的安排真的沒有關係。在這一點上，這肯定與你所鏈接的問題不同，後者假設分區不需要重新排列元素。

Answer 3

我認爲你所擁有的唯一選擇是使用蠻力，可能會進行一些優化（例如the pseudo-polynomial solution to subset sum problem的K = 2的修改版本）以適用於簡單情況。也許有一個更好的算法，但沒有太多更好的。

從閱讀維基百科關於Partition problem和3-partition problem的文章，我發現你的問題是NP的完整性問題，這些問題是一般化和稍微修改過的版本。

更具體地說，如果你有解決你的問題的有效算法，它也將是能夠有效地解決上述兩個問題，這是不可能的（除非P = NP）。

Answer 4

LeetCoder have worked關於由Steven Skiena提供的相同問題定義（和解決方案）。唯一的問題是他用C++進行會話，所以它變得更容易理解。