선호도 기반 그룹화를위한 알고리즘

Question

선호도에 따라 클래스를 분류하는 방법을 생각하고 있습니다.

예를 들어, 각각 다섯 개 가지 클래스 중 하나에 할당 될 예정 100 명 학생들이 말하는 : - 40 석

수학 - 15 석

역사 -

• 과학 15 석
• 컴퓨터 - 20 석
• 쓰기 - 10 석

각 학생에게는 우선 순위에 따라 3 개의 선호 수업이 있습니다. 학생들을 나누는 가장 좋은 방법은 가능한 한 많은 사람들이 1 등석과 2 선발 수업을받는 것과 동시에 어떤 반의 학생들도 방에 너무 많은 학생이 없도록하는 것입니다.

나는 다음과 같은 방법으로 그것을 접근에 대해 생각했습니다

1. 그룹 클래스가 너무 많은 학생들이 자신의 첫 번째 선택 클래스
2. 페이지의 모든 학생들은 너무 몇
3. 확인을 초과 예약 된 클래스에있는 학생에게 예약 취소 클래스가 있는지 확인하십시오.
4. 해당 학생 이동
5. 3 단계 선택 클래스로 2-4 반복

나는 이것이 합리적인 구현이라고 생각하지만, 더 좋은 방법으로이 문제를 해결하는 다른 알고리즘이 있는지 궁금합니다. 나는 온통 검색을 시도했지만 이런 종류의 문제를 해결할 수있는 것을 찾을 수는 없습니다. 당신의 설명에서

Answer 1

이 대단히 Stable Marriage Problem

의 변화 위키 링크를 확인하고 당신은 좋은 인 게일 - 샤플리 알고리즘의 설명을 볼 수 중 하나 같은 소리 해결책. 알고리즘의이 종류와