病みつきになる「動的計画法」、その深淵に迫る：最強最速アルゴリズマー養成講座（2/4 ページ）

[高橋直大，ITmedia]

動的計画法・メモ化再帰の長所と短所

　ナップサック問題を動的計画法で当然のように解いてしまいましたが、前述のように、これ以外にも解き方は無数に存在します。

　例えば、今回は「ある重さにおける最大の価値」を格納しましたが、逆に、「ある価値における最小の重さ」を格納するのもよいでしょう。ある価値に到達するための最小の重さの合計を格納して動的計画法を行えば、求める重さ以下となっている最大の価値を探すことで、同じ答えを求めることができるのです。最初の例でのオーダーは、O（重さの制限*品物数）ですが、こちらの解き方だとO（価値の合計*品物数）となります。また、今回は扱いませんが、メモ化再帰を用いてももちろん同様に解くことが可能です。

　ここまでの説明でピンと来た方も多いかと思いますが、動的計画法では「何をメモリに格納するか」は非常に大切です。重さの制限が異常に大きければ、重さ分のメモリを確保できなくなりますし、価値が大きければ、ある価値に到達するための最小の重さの合計を格納した動的計画法の場合でも同じことが起こります。まして、両方大きな数で構成されていれば、動的計画法で解くことはできません。

　では、全探査で解いた場合はどうでしょうか？　すべての品物に対して、運ぶ／運ばないを考えるので、品物がn個だとすると、重量制限を考えなければ、2^n通りの運び方が存在します。今回の例では、説明のために小さいケースを採用していますが、もし品物が30個程度存在した場合、それだけで破たんしますね。しかし、もし価値や重量が億単位だったとしても、品物が20個以下程度であれば、全探査で解くことも可能です。

　また、動的計画法では、「必要のない要素」まで考えてしまうことが多々あります。例えば、今回の例題では「何番目の品物まで考えたか」を考慮すれば十分ですが、「どの品物を運ぶことにしたか」などを考慮してしまうと、膨大な数となって処理できなくなります。必要のない要素を含めても計算量に問題がなければ一応解くことはできますが、問題をどう分解すればうまく動的計画法を使えるか、をしっかり考えた方が実力につながります。

　このように、解き方の大筋の方針を決めるとき、いわゆる「大局観」が養われているかどうかは重要です。TopCoderで優秀なスコアをたたき出すRedCoderたちは、たいていそうした勘所を外すことはありませんが、それでもたまには判断を誤るものです。筆者の場合も意識してこうした大局観を鍛えてきたという記憶はなく、実戦や日常的な勉強によって、気がついたら大局観が形成されてきたように思います。このため、こうすれば大局観がよくなる、というアドバイスは非常に難しいのですが、さまざまな問題に挑戦したりすることは非常に有意義だと思います。

動的計画法・メモ化再帰チェックシート

　動的計画法・メモ化再帰について解説してきましたが、どの程度理解できたかを確認するための問題を幾つか示します。どう解けばよいかを考えてみてください。ざっと見て解き方がイメージできない場合は、連載第5回から読み直してみることをお勧めします。

• 100万円以下の金額が与えられる。日本の硬貨／紙幣で支払いをする時、支払う合計枚数の最小値を出力しなさい
• ある大小バラバラの1000個以下のビー玉が与えられる。ビー玉の重さが1〜10の整数だとして、これを2人で分けるとき、合計の重さを均等にすることが可能か求めなさい
• コインを1000枚投げたとき、表になっている枚数が480枚以下である確率を求めなさい
• 1×1メートルのタイルで構成されている部屋がある。これに1×2メートルの畳をできるだけ多く敷き詰めたいとき、敷き詰められる畳の最大数を答えなさい
• ある文字列A、Bが与えられる。文字列に対し、「文字を1文字追加する」「文字を1文字削除する」「文字を1文字変更する」の3つの変換が可能なとき、文字列AをBにするための最小の変換数を求めなさい
• 100以上進むとゴールに到達するすごろくがある。1〜6までの1つのさいころを使用してゴールに向かうとき、20回ちょうどでゴールする確率を求めなさい
• 男子が18人、女子が22人いるクラスがある。これをランダムな順番で並ばせた時、女子・男子ともに5人以上が連続して並ばない確率を求めなさい

---

　前回、今回の解説をじっくりと読めば、解き方の大筋の方針がイメージできる問題が増えていると思います。皆さんは幾つの問題に対してイメージできたでしょうか？

　ここではじっくりと考えてもらいたいため、答えは明記しません。ここで取り上げた問題はどれも似たような難易度ですが、分からない場合はほかの問題に当たってみて、慣れてきたころにもう一度考えてみるのもよいでしょう。

　また、前々回の探索のチェックシートで解けなかった問題があれば、そちらにも再度挑戦してみてください。恐らく、分からなかった問題の一部が分かるようになっているはずです。ただし、こちらで取り上げた問題のうち、最後の問題は、コンテストでは存在しませんが、「問題設定が不十分な場合、問題を解くことが不可能である」という部分に気づいてもらいたいという意図で作られた問題なので、解けなくても問題ありません。

　それでは、今回の問題に移りたいと思います。ここまで紹介してきた内容とマッチした問題となっていますので、ぜひ挑戦ください。