Algorithm for preference based grouping

I am looking to figure out a way to sort people into classes by preference.

For example, say there are 100 students that are each going to be assigned one of five classes:

Science - 40 seats

Math - 15 seats

History - 15 seats

Computers - 20 seats

Writing - 10 seats

Each student has three preferred classes that are ordered by preference. What is the best way to approach dividing up the students so that as many people get their first and second choice classes as possible, while at the same time making sure that no class has too many students for the room.

I've thought about approaching it by the following method:

Group all students by their first choice class

See which classes have too many students and which have too few

Check to see if any students in the overbooked classes have second choice classes which are underbooked

Move those students accordingly

Repeat 2-4 with 3rd choice classes

While I feel like this is a reasonable implementation, I am wondering if there are any other algorithms that solve this problem in a better way. I have tried searching all over, but I cannot find anything that would solve this kind of problem.

---

From your description, this sounds very much like one of the variations of the Stable Marriage Problem

Check the Wiki link and you will see a description of the Gale-Shapley Algorithm, which is a good solution.

链接地址: http://www.djcxy.com/p/71322.html

上一篇: 点击输入按钮提交，其他人不提交？

下一篇: 基于偏好的分组算法