这是另一个与动态规划相关的算法问题
问题来了:
找到给定矩阵的最小和，使得在每一行和每一列中选择一个
例如:
3 4 2
8 9 1
7 9 5
最小的一个:4 + 1 + 7
我认为解决方案是网络流量(最大流量/最小切割)，但我认为它不应该像现在这样难
我的解决方案:分离到 n 列表[列]，第 1 列，第 2 列......第 n 列
然后起点 (S) -> column1 -> column2 -> ... -> column n -> (E) end point 并实现最大流量/最小切割
最佳答案
这是 Assignment Problem这可以被认为是图中最小权重完美匹配的一个特例。解决分配问题的经典方法是使用 Hungarian Algorithm .
关于algorithm - 找到在每一行和每一列中只选择一个的矩阵 (n x n) 的最小总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4481961/