查找矩陣中不同行和列的元素總數的最大值

Question

我有一個nxm矩陣，我需要在不同的行和列中查找其值的總和的最大值。

例如考慮下面的矩陣：

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

最大將是12 + 8 + 4 = 24

注意，找到最大和消除屬於該列中的所有的值或行不是一個好的解決方案，因爲它不適用於所有情況。

爲上述異常將是以下：

 m1 m2 
n1 17 1 
n2 18 15 

如果發現18和除去17和15，和將是18 + 1 = 19，而17 + 15 = 32具有更高的值。

關於這個問題算法的任何想法？

Answer 1

解決方案是使用匈牙利算法。這是一個複雜的算法。有一個很好的演講在YouTube上：

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