课程分配算法

Question

我需要为m个课程分配n个人,每个人指定他们的第一和第二个偏好,每个课程都有最多的人参加.每个人只能参加一门课程.该算法应该找到一个解决方案

1. 根据他们的偏好分配一门课程的人数最大化
2. 分配他们的第一选择的人数最大化(考虑到优先级较高的1).

我猜这不是一个不常见的问题,但搜索没有回复太有用,因此我决定推出自己的.这是我到目前为止所得到的:

1. 对于首选项数量少于最多人数的课程,请将所有这些人员分配到课程中
2. 对于其他课程:将随机人员纳入课程,选择该课程作为第一选择,直到课程结束
3. 对于第二选择比自由空间少的课程,将所有这些人分配到课程中
4. 对于其他课程:将随机人员纳入选择该课程作为第二选择的课程,直到课程结束
5. 对于没有课程的每个人:在他们的第一个(然后是第二个)偏好中寻找一个人选择了另一个课程,其中斑点仍然是免费的(如果发现多于一个,则选择选择具有最多免费点的课程的人) ,将此人移至他们的第二选择并指派失踪人员

由于最后一步,我仍然认为该算法不会找到问题的最佳解决方案.任何想法如何使这个更好？还有其他算法可以解决这个问题吗？

Answer 1

如果可能,将每个人都安排在他们的首选课程

如果有人没有得到它,请将它们放在第二个选择中.

现在,我们可能会得到一些没有得到任何选择的人.("失败者".)

找一个有他的第一选择课程的人,这也是"失败者"的第二选择.这个家伙将被重新分配到他的第二选择,而"失败者"将占据他的位置.如果没有这样的人,那么你的问题是无法解决的.

请注意,这样可以最大限度地增加首选人数:

如果你有第二个选择,那么它意味着:

• 别人已经把你的第一选择作为他的第一选择
• 别人将你的第一选择作为他的第二选择,但这只是因为他的第一选择被视为别人的第二选择,并且他的第一选择充满了首选学生.

(可能最后一点有点难以理解,所以这里是重写:)

对于具有第一选择A和第二选择B的人X:

如果X得到选择B,那么:

• Y在A中占据了X的位置,而Y的首选是A.
• Y在A中占据X的位置,而Y的第二选择是A.Y的第一选择是C,但C的位置都充满了其他第一选择C的学生.

Answer 2

这与稳定婚姻问题类似。

给定n 个男人和n 个女人，其中每个人都按照偏好顺序对所有异性成员进行了 1 到n之间的唯一编号排序，将男人和女人结婚在一起，这样就不会有两个异性同时愿意宁愿拥有彼此，也不愿拥有现在的伴侣。如果没有这样的人，所有的婚姻都是“稳定”的。

更新：

考虑到 @bdares 的评论，以及课程容量有限的事实，很难将问题转化为稳定匹配。

我将把这个问题作为一个线性程序来解决，其目标函数基于获得第一选择的人数和课程规模作为约束。