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:

1. Group all students by their first choice class
2. See which classes have too many students and which have too few
3. Check to see if any students in the overbooked classes have second choice classes which are underbooked
4. Move those students accordingly
5. 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.

回答1:

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.