algorithm - 免费分配工作，匈牙利方法行得通吗？

Question

所以我有一个工作分配问题，它没有匈牙利方法所需的传统成本。

例如:

I have 3 workers - A, B and C
I have 5 jobs -  1, 2, 3, 4 and 5

每个 worker 都有一个他可以执行的工作列表，如下所示:

worker A can work on job 1, 2, 5
worker B can work on job 1, 2
worker C can work on job 1

最终结果(因为没有成本)是我可以完成的最大作业数。在这个例子中，我最多可以实现 3 个赋值:

worker A on job 5
worker B on job 2
worker C on job 1

匈牙利法是解决这个问题的好方法吗？我应该只使用“虚拟”成本吗？我在想也许可以用工作偏好的指数作为成本；这是个好主意吗？

Answer 1

匈牙利算法可以在这里工作，但未加权最大二分匹配算法如Hopcroft–Karp会更快。