JAVA - 將int數組分成n組與最低相差

Question

所以我試圖找出一種算法，對用遞歸進行X號的int數組，並把它分成N套方案。這些數字可以是正面的也可以是負面的。這些集合之間需要有最小的差異。例如，如果你給程序的int數組[1,2,3,4]，並告訴它分成3組，然後它將它分成[1,3] [2]和[4]其中集之間的差是2 另一個例子是，如果你給數組[6,6，6，10，10]，並告訴它分成2組，那麼它將把它分成[10，10]和[6，6，6]其中集之間的差異是2.

我們可以假設數組按升序排序（左邊最小，最右邊），因爲排序它將是一個簡單的排序聲明。有任何想法嗎？

編輯：我明白，我正在處理分區問題，我試過了貪婪算法，你從最大到最小的數字，並把他們放在最低的總和，但它不會爲第二個上面給出的例子，所以我正在尋找更可靠的算法。

Answer 1

在更一般的情況（k套）的分區的問題是被稱爲minimum makespan problem。此問題對於k > 2是NP完整的。一個確切的算法，該Graham list scheduling algorithm，是著名的k = 2和k = 3。對於更大的尺寸，如果您未實施NP-complete解決方案，則有number of polynomial-time approximation algorithms。