有效的算法，用於創建一個理想的分佈到容器中的可能溢出的組？

Question

我有一羣學生需要分配到固定容量的教室（比如每個教室有100把椅子）。

每個組只能被分配到一個單一的課堂教學，哪怕是比容量大（即有可能溢出，與學生站起來）

我需要一個算法，使最小的分配溢出和容量不足的教室。

當擁有200組時，執行這種分配的幼稚算法速度極慢，其中約一半的分佈低於教室大小的20％。

任何想法，我可以找到至少一些良好的起點，使此算法閃電般快速？

謝謝！

Answer 1

這與NP完整的bin packing problem類似。很難找到一個快速最優算法，但有可能找到一個快速近似算法。你可以先用一種貪婪的方法 - 把最大的羣體放在第一位，並把它們放到最小的間隙中。