求矩阵 (nxn) 的最小总和，在每一行和每一列中只选择一个
这是与动态规划相关的另一个算法问题，
问题是：
找到给定矩阵的最小和，以便在每一行和每一列中选择一个
例如：
3 4 2
8 9 1
7 9 5
最小的一个：4 + 1 + 7
我认为解决方案是网络流量（最大流量/最小切割），但我认为它不应该那么难
我的解决方案：单独到n列表[列]，列1，列2...列n
然后开始点(S)→第 1 列 ->第 2 列 -> ...->第 n 列 -> (E) 终点 并实施最大流量/最小切割
this is another algorithms problem related to dynamic programming
Here is the problem :
find the minimum sum of the given matrix such that select one in each row and column
For example :
3 4 2
8 9 1
7 9 5
the minimum one : 4 + 1 + 7
I think the solution is network flow (max flow/min cut) but I think it shouldn't be as hard as it is
My solution: seperate to n list[column], column1, column2 ... column n
then start point (S) -> column1 -> column2 -> ... -> column n -> (E) end point
and implement max flow/min cut
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是分配问题，可以被视为图中最小权重完美匹配的特殊情况。解决分配问题的经典方法是使用匈牙利算法。
This is the Assignment Problem which can be considered a special case of minimum weight perfect matching in graphs. The classic way to solve the Assignment Problem is to use the Hungarian Algorithm.