这是与动态规划相关的另一个算法问题
问题是这样的：
找到给定矩阵的最小总和，以便在每一行和每一列中选择一个
例如 ：
3 4 2
8 9 1
7 9 5
最小的一个：4 + 1 + 7
我认为解决方案是网络流量（最大流量/最小切割），但我认为它不应该那么难
我的解决方案：分离到n个列表[列]，column1，column2 ...第n列
然后起点 (S) -> 第 1 列 -> 第 2 列 -> ... -> 第 n 列 -> (E) 终点
并实施最大流量/最小切割
这是分配问题 http://en.wikipedia.org/wiki/Assignment_problem这可以被认为是图中最小权完美匹配的特例。解决分配问题的经典方法是使用匈牙利算法 http://en.wikipedia.org/wiki/Hungarian_algorithm.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
