基于偏好的分组算法

Question

我正在寻找一种方法来根据偏好将人们分类。

例如，假设有 100 名学生，每名学生将被分配到五个类(class)中的一个:

• 科学 - 40 个席位
• 数学 - 15 个席位
• 历史 - 15 个席位
• 计算机 - 20 个席位
• 写作 - 10 个席位

每个学生都有三个首选类(class)，按偏好排序。分配学生的最佳方法是什么，以便尽可能多的人选择第一和第二选择的类(class)，同时确保没有一个类(class)的学生太多。

我考虑过通过以下方法来解决它:

1. 将所有学生按首选类(class)分组
2. 查看哪些类(class)的学生太多，哪些类(class)的学生太少
3. 检查超额预订类(class)中是否有任何学生的第二选择类(class)预订不足
4. 相应地移动那些学生
5. 用第 3 个选择类(class)重复 2-4

虽然我觉得这是一个合理的实现，但我想知道是否还有其他算法可以更好地解决这个问题。我试过到处搜索，但找不到任何可以解决此类问题的方法。

Answer 1

根据您的描述，这听起来很像 Stable Marriage Problem 的变体之一。

检查 Wiki 链接，您将看到 Gale-Shapley 算法的描述，这是一个很好的解决方案。