algorithm - 类(class)分配算法

Question

我需要将 n 个人分配到 m 门类(class)，其中每个人指定他们的第一和第二偏好，并且每门类(class)有最大参加人数。每个人只能参加一门类(class)。该算法应该找到一个解决方案，其中

1. 根据自己的喜好分配一门类(class)的人数最大化
2. 分配给他们第一选择的人数已最大化(考虑到 1 具有更高的优先级)。

我猜想这不是一个不常见的问题，但搜索没有返回任何有用的信息，因此我决定自己动手。这是我到目前为止的想法:

1. 对于第一偏好少于最大参加人数的类(class)，将所有这些人分配给该类(class)
2. 对于其他类(class):将选择该类(class)作为第一选择的随机人员放入类(class)中，直到类(class)满员为止
3. 对于第二偏好少于自由名额的类(class)，将所有这些人分配给该类(class)
4. 对于其他类(class):将选择该类(class)作为第二选择的随机人员放入类(class)中，直到类(class)满员为止
5. 对于每个没有类(class)的人:在他们的第一(然后是第二)偏好中寻找一个选择了另一门类(class)的人仍然有空位(如果找到多个人，选择选择最多的类(class)的人空闲位置)，将此人移至他们的第二选择并分配失踪人员

由于最后一步，我仍然不认为这个算法会找到问题的最优解。任何想法如何使这个更好？有没有其他算法可以解决这个问题？

Answer 1

如果可能，将每个人安排在他们的第一选择类(class)中。

如果有人没有得到它，将他们放在他们的第二选择中。

现在，我们可能会得到一些没有得到任何选择的人。 (“失败者”。)

找一个选了第一门课的人，也是“loser”的第二门课。这家伙将被重新分配到他的第二选择，而“失败者”将占据他的位置。如果没有这个人，那你的问题就无解了。

请注意，这会最大化获得第一选择的人数:

如果您有第二选择，则意味着:

• 其他人已经将您的第一选择作为他的第一选择
• 别人把你的第一选择当成了他的第二选择，只是因为他的第一选择被别人当成了第二选择，而他的第一选择全是第一选择的学生。

(可能最后一点有点难以理解，所以这里改写一下:)

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

如果 X 得到选项 B，则:

• Y 占据了 X 在 A 中的位置，Y 的第一选择是 A。
• Y在A中占了X的位置，Y的第二选择是A。Y的第一选择是C，但是C的位置都被其他第一选择也是C的学生填满了。