我需要一个算法为下面的分布

Question

我需要一个算法来解决以下问题。

我有老师，每个老师都有他们喜欢的科目。例如,

老师1可能更喜欢science, maths and computers

老师2可能更喜欢english and maths

老师3可能更喜欢science, english and maths

就像这样……

我有N数量的答卷。每一个都属于任何一个主题(english, science, maths and computers)。我需要根据每位老师的喜好将这些答卷分配给他们。但我们最多只能分配50篇论文给一位老师。如果我们有1000份答卷，我们将有最低限度的20教师(1000/50)。

如果我们在maths中有112张答卷，如果我们有两个maths偏好的老师，我们可以给他们分配100个，剩下的12个我们可以分配给任何老师(属于非偏好类别)。

这个算法的成功将取决于它根据教师的偏好将答卷分配给他们的效率，以及他们拥有的非首选答卷的数量有多少。

谁能告诉我哪种算法适合它？

Answer 1

这个问题可以表示为一个简单的assignment problem (将n作业分配给n工作者)：

每个教师作为工人出现50次，每个工作表作为作业出现一次。

教师使用weight 0连接到一张工作表，如果这是他的首选科目之一，则使用weight 1。如果workers (50 * number of teachers)比jobs多，则添加虚构的作业(直到workers的数量等于作业的数量)，这些作业连接到所有具有权重0的workers，这些作业可以在解决方案中忽略。

从这一点来看，请参考任何解决赋值问题的算法(请参阅wiki链接)。您希望找到具有最小权重的赋值。