잠재 오버플로가있는 컨테이너에 그룹을 이상적으로 분포시키는 효율적인 알고리즘?

Question

나는 고정 된 수용량의 교실 (예를 들어, 각각 100 명의 의자)에 배정되어야하는 학생들의 그룹을 가지고 있습니다.

각 그룹은이 용량보다 큰 경우에도 하나의 교실에 할당해야

내가 최소 할당을 만들기 위해 알고리즘을 필요

(즉, 학생들이 최대 서 오버 플로우가있을 수 있습니다) 오버 플로우 및 용량 부족 교실.

이 할당을 수행하는 순진한 알고리즘은 약 200 개의 그룹이있을 때 끔찍하게 느리며 그 중 절반 정도가 교실 크기의 20 % 미만입니다.

나는이 알고리즘 번개 빠른 만들기위한 적어도 좋은 출발점을 찾을 수있는 아이디어?

감사합니다.

Answer 1

이것은 NP 완성 인 bin packing problem과 유사합니다. 빠른 최적 알고리즘을 찾는 것은 어렵지만 거의 최적의 알고리즘을 찾는 것이 가능합니다. 욕심 많은 접근 방법을 사용하여 시작할 수 있습니다. 먼저 가장 큰 그룹을 배치하고 가장 작은 간격으로 끼워 넣습니다.