分配偏好

Question

如果n个床位要分配给m个人。每个人可能有多种偏好或根本不喜欢。如何满足最大限度的人。有偏好并且得到相同的人将被记录为满意的人。

我试着用最小的首选床位先分配一个最低偏好的人。有没有我失踪的情况，因为它给了我一个错误的答案？

Answer 1

这是maximum bipartite matching的问题。 Wiki有很好的算法，也可以查询maximum flow。