各行と列で 1 つだけを選択する行列 (n x n) の最小合計を求めます。

Question

これは動的計画法に関連する別のアルゴリズムの問​​題です

問題は次のとおりです。

各行と列で 1 つを選択するように、指定された行列の最小合計を見つけます。

例えば ​​：

3 4 2

8 9 1

7 9 5

最小のもの:4 + 1 + 7

解決策はネットワーク フロー (最大フロー/最小カット) だと思いますが、それほど難しくはないと思います

私の解決策:n list[column]、column1、column2 ...に区切るn列目

開始点 (S) -> 列 1 -> 列 2 -> ...- >列n - >（e）エンドポイントと最大流れ/minカットを実装する

Answer 1

これは 課題の問題 これは、グラフ内の最小重みが完全に一致する特殊なケースと考えることができます。割り当て問題を解決する古典的な方法は、 ハンガリー語アルゴリズム.