【動的計画法】ロッド切り出し問題

12月、1月はCODEVS4に集中してたり、2月はうわおえを更新してたりで、アルゴリズムイントロダクションを勧められていなかったが再開!

動的計画法を解説している書籍やサイトでは、ナップザック問題を取り上げている場合が多い気がする。
でも、ナップザック問題は2次の配列で解くので、その複雑さで躓く人もいるとかいないとか。
しかし、アルゴリズムイントロダクション様が動的計画法の入門として扱っているのは、「ロッド切り出し」という、1次の配列で解ける問題を扱っている。さすが!

この場合に長さがNの1本の金属棒があり、長さiの場合の価格Pi円という価格表がある。
この時、長さnの金属棒を切り出して得られる最大の価格を求めよ

価格表はこうなっている。解説のために、単位は円とした。

i 1 2 3 4 5 6 7 8 9 10
Pi(円) 1 5 8 9 10 17 17 20 24 30

例えば、長さが5の金属棒を分割した時の最高価格は、長さ2と長さ3に切り出したときの価格の合計である13円になる。

この切り出した最高価格はどう求めるんだということで、長さNが1の場合から順番に最高価格を考えていくと、下のような考え方になる。


長さNが1の時。Nが1の時の最高価格は切り出さない場合の1円である。
これは単純。


長さNが2以上の時は、切り出した場合と切り出さなかった場合を比較する必要がある。


Nが2の時の最高価格は、長さ1の価格と長さ1の最高価格の合計か、切り出さなかった場合の価格。


Nが3の時の最高価格は、長さ1の価格と長さ2の最高価格の合計か、長さ2の最高価格と長さ1の価格の合計か、切り出さなかった場合の価格


Nが4の時の最高価格は、長さ1の価格と長さ3の最高価格の合計か、長さ2の最高価格と長さ2の最高価格の合計か、長さ3の最高価格と長さ1の価格の合計か、切り出さなかった場合の価格


Nが5の時の最高価格は、長さ1の価格と長さ4の最高価格の合計か、長さ2の最高価格と長さ3の最高価格の合計か、長さ3の最高価格と長さ2の最高価格の合計か、長さ4の最高価格と長さ1の価格の合計か、切り出さなかった場合の価格


Nが6の時は(ry


Nが7の時は(ry


Nが8の時は(ry


↑ なんか繰り返しっぽいよね。パターンが見えてくる気がする。

ここでdp[]という1次元配列を用意する。dp[n]には、長さnの場合の最高価格を格納するという変数。
このdpを短い長さから埋めていけば、ロッド切り出し問題は解くことが出来る。

これを求めるRubyのコードが以下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 長さNの金属棒を切り出した時の最高価格を求める

PRICES = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30].freeze
N = 10

dp = [0]
(1).upto(N) do |i|
  dp[i] = PRICES[i];

  (1).upto(i) do |j|
    # それまでの最高価格と、長さjで切り出した場合の価格を比較して大きい方をdp[i]とする
    dp[i] = [dp[i], dp[i-j] + PRICES[j]].max
  end
end

p dp[N]
# => 30

こうやって、小さい問題の最善の解を利用して大きい問題を解くのが動的計画法なんだってさ。
そのうちナップザック問題も書くぞー。そんなに変わらないけど。

詳しく書くとめっちゃ長いブログになっちゃうので、発想の過程をかなりはしょているけれど、動的計画法を学習するときは、再帰関数からのメモ化再帰からの漸化式をプログラム化って流れが良いっぽい。
最初から漸化式立てようとすると、数学力のない人は即死する。。