最佳匹配额定配对的最佳方式是什么？

Question

让我说我有一个男人和女人的名单。每个男人（x）对每个女人进行评估，每个女人（y）评估每个男人的评分，评分为0-9。

例如

X1：{Y1：0，Y2：5，Y3：9}

X2：{Y1：1，Y 2：0，Y3：9}

X3：{Y1：5，Y2 ：5，Y3：8}

Y1：{X1：3，X2：3，X3：5}

Y2：{X1：8，X2：2，X 3：2}

Y3 ：{x1：9，x2：5，x3：9}

我正在寻找一种算法，将所有x & y配对为最大化总评分。

在这种情况下，最佳配对将是x2：y3 = 9 + 9 = 18，x1：y2 = 5 + 8 = 13，x3：y1 = 5 + 9 =至少我认为这是由眼睛。

我认为它是最大独立集问题的简化版本，这不是一个NP难的优化问题。

Answer 1

这个问题被称为稳定的婚姻问题，诺贝尔经济学奖被授予解决方案。算法在一些细节描述在Wikipedia：

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 
    } 
}