アルゴリズムのとびら　その3

はじめに

「アルゴリズムのとびら」シリーズの3回目は、前回に引き続き、重さの上限が決まっている中で合計の値段が一番高くなる組み合わせの考え方についてです。前回の解説で述べた通り、お宝の数が増えるにつれて、計算すべき組み合わせの数は指数的に増加します。途中で条件に合わないと分かった組み合わせを計算から省く「枝刈り」の手法以外に、計算を減らす方法はあるのでしょうか？

勇者ねこの冒険

もっと大きな船で、もっとたくさんのお宝を探したい勇者ねこ。でも、お宝の数が増えたら、計算する量ももっと増えてしまいます。

勇者ねこは前回で考えた方法を見直して、もっといい方法がないか考えてみました。

「そういえば、A・B・Cの3つのお宝の重さと値段の合計を計算するときに……」
「先にA・Bの2つのお宝の合計を計算していた気がするな」
「A・Bのときの計算結果をメモしていたら、その結果にCを足すだけでA・B・Cの計算結果になるぞ」
「同じように、A・B・DやA・B・Eでも、A・Bの計算結果メモは使えるぞ」

「さらにA・B・Cの結果もメモしておけば……」
「A・B・C・DやA・B・C・E、A・B・C・D・Eの計算でも使えるぞ！」

「もしA・B・Cの組み合わせでのせられる重さを超えていたら……」
「そのときは前にしたみたいに、A・B・Cが入った組み合わせ（A・B・C・DやA・B・C・E）はもう計算しなくていいよね！」

勇者ねこは、少ない数の組み合わせの計算結果をメモしておけば、多い数の組み合わせを計算するときに楽に計算できることに気が付きました！
さらに、余計な計算を省く方法も組み合わせれば、計算はさらに楽にできます。

どんなメモの書き方ならよりわかりやすくなるでしょうか？　読んでいるあなたも、試しに考えてみてください！

解説

今回勇者ねこが考えた手法は、「動的計画法」「メモ化」と呼ばれる方法です。問題を小さく切り分けて、結果を記録・再利用していくことで効率よく計算していきます。

実際にメモに書いていく場合は、表形式にすると、もれやかぶりを防げます。

次回は、これまでのアルゴリズムを使ったプログラムに代わりに計算してみてもらいます。お楽しみに！