最佳匹配配对的最佳方法是什么？

Question

假设我有一份男人和女人的名单。每个男人(X)给每个女人打分，每个女人(Y)给每个男人打分，从0到9。

例如：

x1：{y1: 0，y2: 5，y3: 9}

x2：{y1: 1，y2: 0，y3: 9}

x3：{y1: 5，y2: 5，y3: 8}

y1：{x1: 3，x2: 3，x3: 5}

y2：{x1: 8，x2: 2，x3: 2}

y3：{x1: 9，x2: 5，x3: 9}

我正在寻找一个算法，配对所有的x和y，以最大化总评级。

在这种情况下，最优配对将是x2:y3 = 9+9 = 18，x1:y2 = 5+8 = 13，x3:y1 = 5+9 = 14。总评级为45。至少我是这样认为的。

我认为这是最大独立集问题的简化版本，不是NP-hard优化问题。

Answer 1

这个问题被称为稳定的婚姻问题，并因解决这个问题而获得了诺贝尔经济学奖。算法在维基百科上有更详细的描述：

http://en.wikipedia.org/wiki/Stable_marriage_problem

从维基百科剪切/粘贴的伪代码：

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}