各セルに数字の書かれたn行n列の表があって、この各セルの数字に下記のルールで丸をつけるとします。
- 1行あたり必ず1つのセルに丸をつけなければならない(0個でも2個以上でも駄目)
- 1列あたり必ず1つのセルに丸をつけなければならない(0個でも2個以上でも駄目)
※ つまり全部でn個のセルに丸がつくことになります
この時、この丸をつけた数字の合計が最大になるようにセルを選択する、効率の良い(全探索ではない)アルゴリズムを考えているのですが、あまり良い考えが浮かびません。
こうすればよいのではという考えや何か既存のアルゴリズムをご存知の方がいましたら、お知恵をお貸しいただけませんでしょうか。
たとえばn=2で表が下記のようになっている場合は、左上のセルと右下のセルを選択するのが解になります。(10+1 > 5+5)
10 5
5 1
また同じくn=2で表が下記のようになっている場合は、右上のセルと左下のセルを選択するのが解になります。(10+1 < 5+7)
10 5
7 1