如何在矩阵中添加数字以产生最小结果？

Question

这更像是算法/数学问题,但我希望在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.

Answer 1

如果您不想自己编写代码，则可以随时使用其他人辛勤工作和友善的出版物。这个 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)