algorithm - 用于将组理想分布到具有潜在溢出的容器中的有效算法？

Question

我有一组学生需要分配到固定容量的教室（例如，每个教室 100 把椅子）。

每个小组只能分配到一个教室，即使它大于容量（即可能会出现溢出，学生站起来）

我需要一种算法来分配最少溢出和容量不足的教室。

当有大约 200 个小组时，进行这种分配的简单算法非常慢，其中大约一半的分配不到教室规模的 20%。

有什么想法可以让我至少找到一些好的起点来使这个算法快如闪电吗？

谢谢！

Answer 1

这类似于装箱问题，它是 NP 完全的。很难找到快速的最优算法，但可以找到快速接近最优的算法。您可以从使用贪婪的方法开始 - 将最大的群体放在首位，然后将它们放入它们适合的最小间隙中。