如何在矩陣中添加數字以產生最小結果？

這是更多的算法/數學問題，但我希望在C++中實現一個解決方案。如何在矩陣中添加數字以產生最小結果？

假設我有一個矩陣，像這樣在點表示整數：

W X Y Z 
A . . . . 
B . . . . 
C . . . . 
D . . . .

我怎麼會產生最小的結果，如果我必須選擇一個數字在每一欄，使得在大多數一號每一行？

例如，我可以選擇AW BX CY DZ或AZ BX CY DW但不是AW BW CZ DZ

蠻力方法似乎取n！計算。有更快的方法嗎？最終我想在大小爲60的矩陣中添加數字。

而且，所有的數字範圍從0到256

來源

2013-07-03 user2445455

確實是n個因子。我的錯。 – Tarik

讓我們假設你以AW，BX或BW，AX開頭：在這兩種情況下，A，B行和W，X列都將被刪除。遞歸思考和緩存結果應該可以做到。見http://en.wikipedia.org/wiki/Dynamic_programming – Tarik

http://en.wikipedia.org/wiki/Hungarian_algorithm 你的問題看起來類似於這個問題。 – user2548103

如果你不想自己的代碼時，你總是可以用別人的辛勤工作，善良的出版物。 Haskell中的這一個，在我的舊筆記本電腦上，在不到十分之二秒的時間內解決了一個60x60的隨機矩陣。多麼好的算法！

import Data.Algorithm.Munkres 
import Data.Array.Unboxed 
import Data.List (transpose) 

solve n matrix = 
    hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)

來源

2013-07-04 05:32:36

如何在矩陣中添加數字以產生最小結果？

回答

相關問題