調度：分區是一個整數集成K個子集

Question

我的工作任務調度，面臨以下的問題（處理器之間的任務分配）：

有一組N個整數。如何將它們劃分成K個不相交的子集，它們的總和相差很小？

我正在尋找一個簡單的啓發式算法，它具有N = 100-500和K = 10-20的合理計算複雜度。在最佳解決方案中不需要（即和的最小可能差異），粗略的近似就足夠了。

在此先感謝。

Answer 1

建設啓發式First Fit或First Fit Decreasing工作良好。

對於First fit Decreasing，首先將大小遞減的部分（在下面的示例中爲A，B，C，D）進行排序，然後將其放入最佳剩餘點（X或Y）中。在下面的示例中，忽略2個維度中的1個（例如，忽略CPU）。

Answer 2

這是你正在尋找的文件，我想：

多路號碼分區
理查德·E·科爾夫
計算機科學系
加州大學洛杉磯分校
洛杉磯，CA 90095 korf@cs.ucla.edu

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.2326&rep=rep1&type=pdf

Answer 3

即使分割成2是NP完全問題。雖然你可以使用僞多項式時間算法。提到on Wikipedia，假設你有數字總和的上限。

Answer 4

事實證明，簡單的greedy algorithm在這種情況下效果很好。