algorithm - 从矩阵中找到最大总和

Question

有一个m行n列的矩阵。任务是找到从每行和每列中选择单个元素的最大总和。我想出了一个解决方案，它从整个矩阵中找到最大值，然后将该行和列设置为零，将其添加到总和中，然后继续寻找下一个最大值。这样重复 m 次。

但这种方法的问题在于是否存在重复元素。我将尝试用一个例子来解释它。这是矩阵..

3 6 5 3
9 4 9 2
8 1 4 3
4 7 2 5

现在，如果我按照上面的方法..总和将是 9 + 7 + 5 + 3 而它应该是 9 + 8 + 7 + 3。如何解决这个问题..我被卡住了

更新:列是可以分配给一个人的座位成本，行是人数。我们想以这样的方式分配它们，以便我们获得最大的成本。

Answer 1

这不就是http://en.wikipedia.org/wiki/Assignment_problem吗？ ，通常由 http://en.wikipedia.org/wiki/Hungarian_algorithm 解决？显然，您想要的是最大值而不是最小值，但是您肯定可以通过最大化成本来实现这一点 -(实际成本)或者，如果您担心 -ve 成本，(矩阵中的最大成本)-(实际成本).