假设您有一个包含 5 个部分的类(class):A、B、C、D、E。每个部分在不同的时间开会，因此注册该类(class)的学生将优先选择他们将参加的部分(他们只能参加一个部分)。当学生注册类(class)时，他们会按优先顺序列出他们更愿意参加的 3 个部分。
每个部分有 n 个学生。为简单起见，假设恰好有 n*5 名学生注册了该类(class)。
因此，问题是:您如何有效地将学生匹配到他们喜欢的部分？
我见过一些具有类似匹配场景问题的问题，但没有一个很合适，恐怕我对算法的了解还不够多，无法自己编写。顺便说一句，这是一个真正的问题，我知道有问题的部门需要几天时间才能手工完成。
最佳答案
为了确定每个学生是否可以被分配到一个preferred section，在下面的网络中构建一个整数值的最大流，其中三个X代表从学生到学生的capacity-1弧他们喜欢的部分(通过多项式时间，例如，推送重新标记算法)。当且仅当最大流量移动 m = n*5 个单位时，才有解决方案；然后分配由每个学生的哪些弧线饱和来确定。
capacity-1 arcs capacity-n arcs
| |
v v
student 1
/ student 2 section1
/ . X section2 \
source < . X section3 > sink
\ . X section4 /
\ student m-1 section5
student m
考虑到偏好顺序，切换到解决最小成本流问题，仍然是多时间可解的(尽管您可能会发现通用 LP 求解器的网络单纯形模式更容易使用)，它允许为每个弧指定的成本。根据您认为公平的程度，为每个偏好级别选择一个分数。
我确定之前有人问过这个问题，但是排期问题就像雪花一样，光靠关键词是找不到老问题的。
关于algorithm - 如何有效地将学生匹配到他们喜欢的部分？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18181753/