分裂組儘可能均勻

Question

我有n組。每組中的項目數可以說是c1，...，cn。我需要將它分成k個相同大小的新組（大小偏差+/- d％），以便我可以最小化每個新組中的舊組的數量，即min [總和（每個k中的c）]。

你有什麼想法？也許一些標準算法？對於模糊的問題抱歉。我很想回答有關細節的任何問題。

在此先感謝！

Answer 1

讓總人數爲m。如果原來的羣體是大致相同的尺寸，這個簡單的程序應約儘量減少任何新的組同老一羣人的最大數量：

• 若m/k是小數，那麼一些新的羣體需要比其他人多1人。令e = m - roundDown（m/k）* k。將會有一個更大的新組，我們將（任意）首先選擇。
• 排列人物，以便舊組形成行，並且行是「左對齊」的。行和每行內人員的順序無關緊要。
• 從左上角開始，沿着最左側的列向下添加人員到第一個新組。如果您到達最低點，但您仍然沒有爲這個新組選擇roundDown（m/k）+1人，請繼續在第二列的頂部等。如果您遇到「洞」（因爲該行在這個專欄位置已經完成了左邊的某個位置），只是繼續往下走。基本上這意味着來自同一個老組（行）的任何兩個人將他們組成同一個新組，他們儘可能相距甚遠。
  • 對第一組新的組重複此操作。
  • 對於剩餘的k-e個新組，請按照相同的方式進行，但每個組只能選擇roundDown（m/k）個人。