2次元配列全体で最大の合計

Question

2次元整数配列全体で可能な限り高い合計を見つける最良の方法は何ですか？列と行を繰り返すことはできません。例えば。

1 3 6 
4 5 2 
3 1 3 
Max sum: 3+5+6=14 

ハンガリーのアルゴリズムと呼ばれる方法がありますが、これは最小合計を見つけるのに適しているようです。

Answer 1

はい、ハンガリーのアルゴリズムを使用できます。

最小の検索ではなく、最大の合計を検索する検索条件を変更する必要があります。 Dijkstraの代わりにBellman-Fordを検索コンポーネントに使用する必要があります（Dijkstraは最大合計パスを計算できないため）。

選択されたノードがすでに最大値を使用してペア設定されているため、変更が発生すると合計合計が低くなるため、常に増加するループに入ることはできません。既に接続されたノードからの損失が新たに接続されたノードからの利得よりも小さい場合、アルゴリズムは接続を再配置することを選択する。あなたはそれについて心配する必要はありません。