我正在处理最大二分匹配问题的一个变体。 原问题如下:
有 M 个求职者和 N 个职位。每个申请人都有他/她感兴趣的工作子集。每个职位空缺只能接受一个申请人，并且只能为一个职位任命一个职位申请人。为求职者分配工作，以便尽可能多的求职者找到工作。
附加约束是:
每个申请者都属于一个特定的组。现在，我们想要最大化快乐组的数量，而不是最大化申请人的数量。快乐的群体是所有求职者都能找到工作的群体。
欢迎任何想法/讨论!
最佳答案
与永恒的联系
如果你能解决这个问题，你可能会在 Eternity puzzle 上赢一百万英镑.
在这个谜题中，您必须将 209 个多边形拼到一 block 棋盘上。
缩减是为每个 block 和位置的组合分配一个组。
每个小组都有一个领导者，他只对与演奏他的作品相对应的工作感兴趣。
每个组也有一个人负责瓷砖中的每个方 block :该人只对填充游戏板上相应方 block 的工作感兴趣。
如果你能找到 209 个快乐组的解决方案，那么你就找到了这个难题的解决方案!
独立集的连接
这是 NP-hard 因为它可以用来解决 maximum independent set这是一个已知的 NP-hard 问题。
假设我们有一个图，我们想在其中找到最大独立集。
为每条边做一个作业。
为每个顶点创建一个组。
假设顶点 x 连接到三个边 a,b,c。我们将 3 人添加到组 x。每个人只对一份工作感兴趣。第一个对工作 a 感兴趣，第二个对工作 b 感兴趣，第三个对工作 c 感兴趣。
然后找到最大的快乐组就相当于最大的独立集。
关于算法 - 最大二分匹配的变体，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43086310/