キンサクプログラマー

お金儲けと技術のメモ

動的計画法(Dynamic Programing(DP))の話 その1

 動的計画法って難しい。何度読んでもイマイチ身にならない。
なので、ちゃんと理解するために書き残していこうと思う。

動的計画法とは

TopCoderやCodeJamといったアルゴリズムコンテンストによく出るアルゴリズム
愚直に(たとえば全探索)などの方法ではTLE(time limit exceeded)してしまうような問題を、サクッと出すことができる(うまくいけば)。簡単に言うと、漸化式のようなものだと思えば当たらずとも遠からず。

  • メモ化(再起による計算をするが、一度解いた問題はメモしておくことで、高速化する)
  • 分割統治法(小さな問題を徐々に大きくしていく)

の2パターンがあるが、本質的には同じやり方。
メモ化については、再起呼び出しをするためスタックを食いつぶす恐れがあるが、なんというかイメージがしやすい。
分割統治法の方がスタックオーバーの恐れなどはないものの、なんというか理解しにくい。配列のインデックス内で引き算とかするのが個人的には苦手。

ナップサック問題(Knapsack Problem)

ナップサックのスペルがKnapsackということを初めて知った。
現代の子供達はナップサックを使うのかもよくわからないが、このナップサック問題は基本的に以下のような形体をとる。

    • 耐久11kgのナップサックがあります
    • 忍び込んだ部屋にはパソコン、プレイステーション、時計、カメラがあります
    • それぞれ、重さは2kg、10kg、5kg、6kg
    • 一方でお値段は、それぞれ、1万円、10万円、6万円、7万円
    • ナップサックに可能な限り高価になるように詰め込んでください

ちょっと考えてみよう

何も知らない人はまず、「よっしゃ、一番高いもんいれたろ!」ということになるが、
ここて10kg、10万円のプレーステーションをいれてしまうと、その時点でナップサックに追加できるものがなくなってしまうが、これは正解ではない。正解は時計とカメラのペア=13万円だ。軽さ重視で詰め込んでいっても同様の問題にすることは自明だろう。

 そこまで考えた人は多分、「よっしゃ全通り考えたろ!」と思うに違いない。
ここで、全通りの組み合わせを考えた場合、
パソコン        入れる or 入れない
プレイステーション   入れる or 入れない
時計          入れる or 入れない
カメラ         入れる or 入れない
の2*2*2*2の16通となる。

16通り程度であれば余裕だが、盗めるものが10個あるだけで1000通りを越えてしまう。
しかも、アルゴリズムコンテストで出題されるような内容では100個など、全探索では解けない内容になっていることが多い。
それではどうするか・・・

もちろん動的計画法で解くしかない。

基本アイデア

11kgの時の最大価値を調べるというのは、先ほどの例から考えるとちょっと難しそうだが、
1kgの時の最大価値から考えれば簡単だ。

1kgの場合、なんもはいらないので0円
2kgの場合、パソコンがはいった!   1万円
3kgの場合、どちらにしろパソコンだけだ1万円
4kgの場合、あきはあるがパソコンだけか1万円
5kgの場合、お!時計が入る!     6万円
6kgの場合、む。カメラがはいるぞ   7万円
7kgの場合、時計とパソコンもはいるぞ!8万円
8kgの場合、同じ!          8万円
   ・・・・

重さを徐々に増やしていきながら、物を突っこむべきか否かを判断するだけ。

Rubyで書いた
github.com