基于偏好的分组算法

Question

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

例如，假设有100名学生，其各自将被分配五类之一：

• 科学 - 40席
• 数学 - 15席
• 历史 - 15席
• 电脑 - 20席
• 写作 - 10席

每个学生都有三个首选的班级，按照偏好排序。最好的办法是分开学生，让尽可能多的人获得他们的第一和第二选择课程，同时确保没有班级的学生太多。

我想过通过下面的方法接近它：

1. 集团所有的学生通过他们的第一选择类
2. 看哪个班有太多的学生和具有太少
3. 检查到查看超额预定班的任何学生是否有已预订的第二选择课程
4. 相应地移动这些学生
5. 重复2-4与第三选择课

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

Answer 1

从您的描述，这听起来很像的Stable Marriage Problem

变化检查维基链接，你会看到盖尔 - 沙普利算法，这是一个很好的描述之一解。