分配2个项目的最大匹配度

Question

派对上共有N人。每个人都有一些食物和饮料的喜好。鉴于特定人员喜欢的所有类型的食物和饮料，找到可以分配饮料和他们选择的食物的最大数量的人。

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

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

Answer 1

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

构建2二部图G和G'使得：对于G：第一部分集合是P，第二部分集合是F，对于G'：第一部分集合是P，第二部分集合是D.分别对G和G'进行最大匹配。在M上调用M的最大匹配，在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。