algorithm - 分配 2 个项目的最大匹配

Question

聚会上有N个人。每个人都有一些对食物和饮料的偏好。给定一个特定的人喜欢的所有类型的食物和饮料，找出可以分配给他们选择的饮料和食物的最大人数。

一个人可能对食物和饮料都有多种选择，例如，一个人可能喜欢食物 A、B、C 和饮料 X、Y、Z。如果我们将 (A,Z) 分配给该人，我们认为该人已被正确分配。

考虑到我们需要处理两个约束，我们如何解决这个问题。

Answer 1

设 F 是所有食物的集合，D 是所有饮料的集合，P 是所有人的集合。

构建 2 个二分图 G 和 G' 使得:对于 G:第一个部分集是 P，第二个部分集是 F，对于 G':第一个部分集是 P，第二个部分集是 D。分别对 G 和 G' 进行最大匹配。称 M 为 G 上的最大匹配，M' 为 G' 上的最大匹配。 M 是一个顶点对列表:(p1, f1), (p2,f2)... 其中 pi 和 fi 分别是人和食物。 M'也是一个顶点对列表:(p1,d1), (p3,d3) ...

现在，将 M 和 M' 合并为同一个人:(p1,f1) + (p1,d1) = (p1,f1,d1)，这就是 p1 的食物-饮料组合。假设 p2 与 f2 有匹配但 p2 在 G' 中没有匹配(不喝酒)，则忽略它。

二分图匹配的一个很好的算法是 Hopcroft-Karp 算法。 http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm .