迭代/递归问题？

我正在研究一个有两个2d阵列的程序。一个叫做男性和一个女性。他们都是3x3大小。该数组包含一个人喜欢另一个人的分数。迭代/递归问题？

即（雄性阵列）。这意味着male0喜欢female0 8，male0喜欢female1 5，male0喜欢女二8，male1喜欢female0 9，male1喜欢female1 5，等等....

8 5 8 
    9 5 7 
    5 6 8

我也有这样的女性，他们评价男性这样的另一个数组。

然后，再拍二维数组，我添加的得分为每个女性（I，J）和男性（I，J）

如何去找出哪些组合提供了最大的总得分？我想拿出像

Best combination is: 
male0 -> female2 
male1 -> female0 
male2 -> female1

2010-09-26 user69514

这听起来像一个配对问题，这是NP完整的。蛮力可能是唯一的方法。 – JoshD 2010-09-26 06:47:53

如果可以的话，我会把它标记为家庭作业。 – 2010-09-26 07:24:06

一种方法是尝试女阵列的每一个排列，每个排列找到总成绩，并在年底选择，让分数最高的排列。

2010-09-26 06:49:53 Reinderien

我同意。有六种方式可以让男人与女人成对（在这种情况下），所以它会相当快。如果我没有弄错，这也是最有效的一般方法。（保存每对的分数将有助于在更大的情况下加快速度，但它仍然是一个O（n！）问题。） – JoshD 2010-09-26 06:53:52

2010-09-26 07:13:28 McTrafik

“最大加权匹配不一定要稳定，但在某些应用中，最大加权匹配更好比一个稳定的。“ – ide 2010-09-26 07:17:22

回答