11

这是另一个与动态规划相关的算法问题

这是问题所在:

找到给定矩阵的最小和,使得在每一行和每一列中选择一个

例如 :

3 4 2

8 9 1

7 9 5

最小的一个:4 + 1 + 7

我认为解决方案是网络流量(最大流量/最小切割),但我认为它不应该像现在那么难

我的解决方案:单独到 n list[column], column1, column2 ... column n

然后起点 (S) -> column1 -> column2 -> ... -> column n -> (E) 终点并实施最大流量/最小切割

4

1 回答 1

16

这是指派问题,可以认为是图中最小权重完美匹配的一种特殊情况。解决分配问题的经典方法是使用匈牙利算法

于 2010-12-19T07:34:43.777 回答