除外テーブルの最大合計スコア

Question

正の値が入力されたn行m列のグリッドがあるとします。グリッドからmin（n、m）の正方形を選択し、選択すると正方形の行と列を削除します。あなたの得点は、あなたが選んだ四角形の値の一部です。私は可能な限り最大のスコアを見つけようとしています。すべての可能性を踏む以外にこれを行う方法はありますか？もし私がすべてを通って列挙しなければならない場合、それを行う最も効率的な方法は何ですか？私はそれが違いがあれば、これをPythonで実装しようとしています。ありがとう。

Answer 1

これはfinding a maximum matching in a weighted bipartite graphに相当します。行と列はグラフのノードに対応し、table[u][v]が0以外の値xを持つ場合、行ノードuと列ノードvの間には重みxがあります。最大一致で選択されたエッジは、選択する非ゼロセルに対応します。一致する部分の幅がmin(n, m)未満の場合は、表のセルの残りのオプションはすべて値が0なので、残りのセルは任意に選択できます。 （テーブルに負のエントリがある場合は、グラフを構築する前にすべてのエントリが非負であることを確認するために、すべてのテーブルエントリを上に調整する必要があります）。NetworkXやigraphのようなグラフライブラリは、テーブルをグラフに変換し、困難な作業をライブラリに委譲することができます。