这更像是一个算法/数学问题,但我希望用 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。
最佳答案
如果您不想自己编写代码,您总是可以使用其他人的辛勤工作和友善的出版物。 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)
关于c++ - 如何在矩阵中添加数字以产生最小结果?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17456862/