1

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

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

老师 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)。

如果我们有 112 张答题纸，maths并且如果我们有两位老师有maths偏好，我们可以为他们分配 100 个，其余的 12 个我们可以分配给任何老师（属于非首选类别）。

该算法的成功将取决于它根据教师的偏好向教师分配答题纸的效率，以及他们有多少不喜欢的答题纸。

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

4

1 回答 1

3

这个问题可以表述为一个简单的分配问题（将n工作分配给n工人）：

每位教师作为工人出现 50 次，每张纸作为工作出现一次。

如果老师是0他喜欢的科目之一，则将其与带有权重的工作表相关联，1如果不是，则将其连接到权重。如果工人 ( 50 * number of teachers) 多于工作，则添加与重量为 的所有工人相关的虚构工作（直到工人数量等于工作数量）0，这些工作可以在解决方案中忽略。

从这一点开始，请参考任何解决分配问题的算法（请参阅 wiki 链接）。您想找到权重最小的作业。

于 2013-11-07T11:06:03.147 回答