algorithm - 用于将组理想分配到可能溢出的容器中的有效算法？

Question

我有几组学生需要分配到固定容量的教室(例如，每组 100 张椅子)。

每个小组只能分配到一个教室，即使它大于容量(即可能会溢出，学生站着)

我需要一种算法来进行分配，以最大限度地减少溢出和容量不足的教室。

当有大约 200 个小组时，执行此分配的朴素算法速度非常慢，其中大约一半的分配不到教室大小的 20%。

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

谢谢!

Answer 1

这类似于 bin packing problem ，这是 NP 完全的。很难找到一个快速的最优算法，但有可能找到一个快速的接近最优的算法。您可以从使用贪心法开始 - 首先放置最大的组，然后将它们放入它们适合的最小间隙。