找到的矩阵（n×n个）的最小总和仅选择一个每行和列中 [英] find the minimum sum of matrix (n x n) that select only one in each row and column

问题描述

这是另外一个算法问题，涉及到动态规划

this is another algorithms problem related to dynamic programming

下面的问题：

找到给定的矩阵的最小总和，使得选定的一个每一行和列中

find the minimum sum of the given matrix such that select one in each row and column

例如：

3 4 2

8 9 1

7 9 5

最小的一个：4 + 1 + 7

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

我的解决办法：单独为n列表[专栏]，列1，列2 ... n列

My solution: seperate to n list[column], column1, column2 ... column n

然后开始点（S） - >列1 - >列2 - > - > n列 - >（E）的终点 并实现最大流/分钟下调

then start point (S) -> column1 -> column2 -> ... -> column n -> (E) end point and implement max flow/min cut

推荐答案

这是分配问题这算是在图表最小重量完美匹配的一个特例。经典的方式来解决分配问题是使用匈牙利算法。

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.

这篇关于找到的矩阵（n×n个）的最小总和仅选择一个每行和列中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！