分配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。