ナップサック問題を動的計画法で当然のように解いてしまいましたが、前述のように、これ以外にも解き方は無数に存在します。
例えば、今回は「ある重さにおける最大の価値」を格納しましたが、逆に、「ある価値における最小の重さ」を格納するのもよいでしょう。ある価値に到達するための最小の重さの合計を格納して動的計画法を行えば、求める重さ以下となっている最大の価値を探すことで、同じ答えを求めることができるのです。最初の例でのオーダーは、O(重さの制限*品物数)ですが、こちらの解き方だとO(価値の合計*品物数)となります。また、今回は扱いませんが、メモ化再帰を用いてももちろん同様に解くことが可能です。
ここまでの説明でピンと来た方も多いかと思いますが、動的計画法では「何をメモリに格納するか」は非常に大切です。重さの制限が異常に大きければ、重さ分のメモリを確保できなくなりますし、価値が大きければ、ある価値に到達するための最小の重さの合計を格納した動的計画法の場合でも同じことが起こります。まして、両方大きな数で構成されていれば、動的計画法で解くことはできません。
では、全探査で解いた場合はどうでしょうか? すべての品物に対して、運ぶ/運ばないを考えるので、品物がn個だとすると、重量制限を考えなければ、2^n通りの運び方が存在します。今回の例では、説明のために小さいケースを採用していますが、もし品物が30個程度存在した場合、それだけで破たんしますね。しかし、もし価値や重量が億単位だったとしても、品物が20個以下程度であれば、全探査で解くことも可能です。
また、動的計画法では、「必要のない要素」まで考えてしまうことが多々あります。例えば、今回の例題では「何番目の品物まで考えたか」を考慮すれば十分ですが、「どの品物を運ぶことにしたか」などを考慮してしまうと、膨大な数となって処理できなくなります。必要のない要素を含めても計算量に問題がなければ一応解くことはできますが、問題をどう分解すればうまく動的計画法を使えるか、をしっかり考えた方が実力につながります。
このように、解き方の大筋の方針を決めるとき、いわゆる「大局観」が養われているかどうかは重要です。TopCoderで優秀なスコアをたたき出すRedCoderたちは、たいていそうした勘所を外すことはありませんが、それでもたまには判断を誤るものです。筆者の場合も意識してこうした大局観を鍛えてきたという記憶はなく、実戦や日常的な勉強によって、気がついたら大局観が形成されてきたように思います。このため、こうすれば大局観がよくなる、というアドバイスは非常に難しいのですが、さまざまな問題に挑戦したりすることは非常に有意義だと思います。
動的計画法・メモ化再帰について解説してきましたが、どの程度理解できたかを確認するための問題を幾つか示します。どう解けばよいかを考えてみてください。ざっと見て解き方がイメージできない場合は、連載第5回から読み直してみることをお勧めします。
前回、今回の解説をじっくりと読めば、解き方の大筋の方針がイメージできる問題が増えていると思います。皆さんは幾つの問題に対してイメージできたでしょうか?
ここではじっくりと考えてもらいたいため、答えは明記しません。ここで取り上げた問題はどれも似たような難易度ですが、分からない場合はほかの問題に当たってみて、慣れてきたころにもう一度考えてみるのもよいでしょう。
また、前々回の探索のチェックシートで解けなかった問題があれば、そちらにも再度挑戦してみてください。恐らく、分からなかった問題の一部が分かるようになっているはずです。ただし、こちらで取り上げた問題のうち、最後の問題は、コンテストでは存在しませんが、「問題設定が不十分な場合、問題を解くことが不可能である」という部分に気づいてもらいたいという意図で作られた問題なので、解けなくても問題ありません。
それでは、今回の問題に移りたいと思います。ここまで紹介してきた内容とマッチした問題となっていますので、ぜひ挑戦ください。
Copyright © ITmedia, Inc. All Rights Reserved.