我有一个应用程序，人们可以在其中互相打分，满分十分。每天午夜，我想为每个成员计算一个"匹配"。我想让每个人都尽可能快乐，平均而言。
So at the midnight, I have an oriented graph like so :
1 -> 2 : 7.5 // P1 give a 7.5/10 to P2
1 -> 3 : 5
1 -> 4 : 9
2 -> 3 : 6
2 -> 1 : 4
etc.
为了使事情更简单，假设如果 P1 给 P2 一个 5，P2 给 P1 一个 7，匹配 P1 - P2 的权重为 5 + 7 - (7-5)/2 = 11(我减去差值，因为对于相同的成绩总和，最好是它们彼此接近，也就是说， a (7/10 - 7/10) 比 a (10/10 - 4/10))更好)。
因此，完成此操作后，我们得到了一个非定向图。从数学上讲，就我的目的而言，我认为我需要找到一种算法，该算法可以在具有此图的所有最大大小匹配中找到具有最大权重总和的匹配。这样的算法存在吗？
我已经研究了"Mariage稳定问题"和"分配问题"，但这些是针对可以分为2类(男性/女性，男性/任务.)的图形。
一种方法是修改图形，然后在其上找到最大权重匹配。
我需要找到一种算法，该算法可以在具有此图的所有最大大小匹配中找到具有最大权重总和的匹配。这样的算法存在吗？
让我们考虑你的图表G = (V, E, w)其中w是你的权重函数。让我们通过nV的大小来表示，即图中的顶点数，并通过M边之间的最大权重来表示。
然后，您所要做的就是以这种方式定义w'：对于E的任何边e，w'(e) = w(e) + n*M。
在这种情况下，G' = (V, E, w')上的最大重量匹配对应于G = (V, E, w)中最大尺寸的匹配，该匹配也具有最大权重。