algorithm - 需要以下分布的算法

Question

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

我有老师，每个老师都有自己喜欢的科目。例如，

老师 1 可能更喜欢科学、数学和计算机
老师 2 可能更喜欢英语和数学
老师 3 可能更喜欢科学、英语和数学
像这样……

我有 N 张答题纸。每个都属于任何一门学科(英语、科学、数学和计算机)。我需要根据他们的喜好将这些答题卡分配给每位老师。但是最多我们可以给一位老师分配 50 篇论文。如果我们有 1000 张答题纸，我们将至少有 20 名教师 (1000/50)。

如果我们有 112 张数学的答题纸，并且如果我们有两位老师有数学的偏好，我们可以给他们分配 100 张，剩下的 12 张我们可以分配给任何老师(属于非首选类别)。

该算法的成功将取决于它根据教师的偏好将答题卡分配给教师的效率，以及他们有多少非首选的答题卡。

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

Answer 1

这个问题可以表述为一个简单的 assignment problem (将 n 个工作分配给 n 个 worker ):

每位教师作为 worker 出现 50 次，每张工作表作为工作出现一次。

如果教师偏爱的科目之一是权重 0，则权重为 1，否则老师将连接到权重为 1 的表单。如果 worker 数(50 * 教师数)多于作业，则添加虚构的作业(直到 worker 数等于作业数)，这些作业连接到权重为 0 的所有 worker ，这些作业在解决方案中可以忽略。

从这一点出发，引用解决分配问题的任何算法(参见 wiki 链接)。你想找到权重最小的分配。