在不同的行和列中找到矩阵中元素总和的最大值 [英] Finding The Max of sum of elements in matrix in distinct rows and columns

问题描述

我有一个nxm矩阵，我需要在不同的行和列中找到其值的总和。

I have a nxm matrix and I need to find the maximum of sum of its values in distinct rows and columns.

例如，考虑以下矩阵：

      m1 m2 m3
n1    1  2  3
n2    4  5  6
n3    7  8  9
n4    10 11 12

最大为12 + 8 + 4 = 24

The max will be 12+8+4 = 24

请注意，找到最大值并消除属于该列或行的所有值并不是一个好的解决方案，因为它不适用于所有情况。

Note that finding the max and eliminating all values belonging to that column or row is not a good solution as it doesn't work for all cases.

上述情况除外：

     m1  m2
n1   17  1
n2   18  15 

如果找到18并删除17和15，则总和为18 +1 = 19，而17 + 15 = 32的值更高。

If you find 18 and remove 17 and 15, the sum will be 18+1 = 19. while 17+15 = 32 has a higher value.

对这个问题的算法有任何想法吗？

Any idea about the algorithm for this question?

推荐答案

解决方案是使用匈牙利算法。这是一个复杂的算法。在youtube上有一个很好的讲座：

The solution is to use Hungarian Algorithm. It's a complicated algorithm. There's a very good lecture on that on youtube:

http://www.youtube.com/watch?v=BUGIhEecipE

这篇关于在不同的行和列中找到矩阵中元素总和的最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！