Эффективный алгоритм создания идеального распределения групп в контейнеры с потенциальным переполнением?

Question

У меня есть группы студентов, которые должны быть распределены по классам с фиксированной вместимостью (скажем, по 100 стульев в каждой).

Каждая группа должна быть распределена только в одной аудитории, даже если она больше вместимости (т. Е. Может быть переполнение при стоящих учениках)

Мне нужен алгоритм для распределения с минимальными переполнениями и классами с недостаточной пропускной способностью.

Наивный алгоритм для такого распределения ужасно медленен, когда в нем ~ 200 групп, причем распределение около половины из них составляет менее 20% от размера аудитории.

Есть идеи, где я могу найти хоть какую-то хорошую отправную точку для молниеносного ускорения этого алгоритма?

Спасибо!

Answer 1

Это похоже на проблему упаковки бункера , которая является NP завершенной. Трудно найти быстрый оптимальный алгоритм, но можно найти быстрый почти оптимальный алгоритм. Вы можете начать с использования жадного подхода - сначала разместите самые большие группы и поместите их в наименьшее расстояние, в которое они вписываются.