用于将组理想分配到具有潜在溢出可能性的容器中的有效算法？
我有一些学生小组需要被分配到固定容量的教室（例如，每个教室 100 张椅子）。
每个小组只能分配到一个教室，即使它大于容量（即可能会溢出，学生站起来）
我需要一种算法来进行分配，以最小化溢出和容量不足的教室。
当有大约 200 个小组时，进行这种分配的简单算法会非常慢，其中大约一半的小组分布在教室规模的 20% 以下。
有什么想法可以让我至少找到一些好的起点来使这个算法快如闪电吗？
谢谢！
I have groups of students that need to be allocated into classrooms of a fixed capacity (say, 100 chairs in each).
Each group must only be allocated to a single classroom, even if it is larger than the capacity (ie there can be an overflow, with students standing up)
I need an algorithm to make the allocations with minimum overflows and under-capacity classrooms.
A naive algorithm to do this allocation is horrendously slow when having ~200 groups, with a distribution of about half of them being under 20% of the classroom size.
Any ideas where I can find at least some good starting point for making this algorithm lightning fast?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这类似于装箱问题，属于NP完全问题。找到一个快速的最优算法是困难的，但是找到一个快速的近乎最优的算法是可能的。您可以从使用贪婪方法开始 - 将最大的组放在前面，然后将它们放入它们适合的最小间隙中。
This is similar to the bin packing problem, which is NP complete. It is difficult to find a fast optimal algorithm but it is possible to find a fast nearly optimal algorithm. You can start by using a greedy approach - placing the largest groups first and putting them into the smallest gap they fit in.