有效的算法来创建一个理想的分布到可能溢出的容器中的组？

Question

我有几组学生需要分配到固定容量的教室里(比如每个教室有100把椅子)。

每组只能分配到一个教室，即使它超过了容量(即可能有学生站着)

我需要一个算法来进行分配与最小的溢出和不足的教室。

当有大约200个组时，执行这种分配的幼稚算法慢得可怕，其中大约一半的组分布在教室大小的20%以下。

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

谢谢!

Answer 1

这类似于bin packing problem，它是NP完全的。很难找到一个快速的最优算法，但有可能找到一个快速的接近最优的算法。你可以从贪婪的方法开始-把最大的组放在第一位，然后把他们放在他们适合的最小的空隙中。