動的計画法

月謝3500円のそろばん塾で出たチャレンジ問題（動的計画法で）

　この記事の続きです。

　Arigataさんが書かれたエントリをフムフムと呼んでいて、MSのソルバに興味を持ちつつ、そもそも「部分和問題」という言葉も「ナップザック問題」という言葉も知らなかった自分の不勉強に恥じ、ちゃんと勉強しないとなぁ・・・と考えているだけの日々を送っていたのですが、何の因果か「アルゴリズムを学ぼう」などという本が絶好のタイミングで出てしまい、この中にこの「ナップザック問題」の解説が乗っていたので、これを参考にF#で「動的計画法」を使った解法を試してみることにしました。

　お題自体は前回のこのエントリと同じです。

　まず基礎知識として、このそろばん塾の問題は、「部分和問題」という有名なカテゴリに属する問題で、金額の部分が整数でない場合には「NP完全」という、要素数が上がるにつれ幾何級数的に計算量が増えていく性質を持っているということです。

　ただし、次のようないくつかの制限が許される場合は、劇的に計算量を減らすアルゴリズムが知られています。このアルゴリズムが今回のお題となっている「動的計画法（Dynamic Programming）」です。

金額の部分が整数でかまわない（重さのように少数点の値を考慮しない）。
とにかくひとつ解が見つかればよい。見つからない場合はリミットを超えない範囲で最大の値がわかればよい。

　動的計画法については「アルゴリズムを学ぼう」や他のサイトに詳しい解説がありますので、そちらを参照してもらったほうがいいと思います。
　「アルゴリズムを学ぼう」は、限られたページで沢山のアルゴリズムを紹介しようとするあまり、一つ一つの解説は少な目となっており、動的計画法もこの本を読んだだけではちょっとわかりづらいかもしれません。動的計画法はとても有名なアルゴリズムなので解説ページも多いのですが、僕は「Gushwell's C# Programming Page」や「Algorithms with Python」のの下半分にある説明が一番わかりやすい気がしました。下のサンプルも、この説明と「アルゴリズムを学ぼう」の説明を読んで頭に入れ、電車の中で書き起こしたものです。

実装

let goods = [ ("プロ野球", 19373)
              ("ディズニーランド", 20453)  ～　　前回のものを使用　　～

let max3f x y z f = let max_xy = max x y in if z > max_xy then f () ; z else max_xy

let dp l target =
  let ar : int array  = Array.zeroCreate (target + 1)
  let g : (string * int) array  = Array.zeroCreate (target + 1)
  for gds in l do
    let wk = snd gds
    for w in [target..(-1)..1] do
      ar.[w] <- max3f
                  ar.[w]
                  ar.[w - 1]
                  (if w >= wk then ar.[w - wk] + wk else 0)
                  (fun () -> g.[w] <- gds)
//    printfn "%A" ar
  ar, g

let rec pp (g : (string * int) array) (ar : int array) pnt =
  printfn "%A" g.[pnt]
  if ar.[pnt] > (snd g.[pnt]) then pp g ar (ar.[pnt] - (snd g.[pnt]))

let solve total =
  let res, g = dp goods total
  pp g res total

solve 150000

実行結果は以下のようになります。

("にくまん", 155)
("机いす", 67275)
("リポD", 1737)
("CDプレーヤー", 36307)
("電動歯ブラシ", 4282)
("たこ焼き", 534)
("ピアニカ", 3351)
("回転ずし", 15906)
("ディズニーランド", 20453)

val dp : seq<string * int> -> int -> int array * (string * int) array
val pp : (string * int) array -> int array -> int -> unit
val solve : int -> unit
val it : unit = ()

ざっくりとした解説

　最初の関数max3fは、三つの数と関数(unit->unit)を引数にとります。三つの引数のうち、最大の値を返すのですが、最後の数が一番大きかった場合だけ、引数で渡された関数を実行する機能を持っています。

　二つ目の関数dpがこのプログラムの心臓部です。金額（150000）ぶんの配列を用意し、それぞれの金額ごとにどのように商品を買うのが一番いいかを考えていきます。

　forループが２段になっていますが、外側では商品リストについて、内側では金額ごとのループを回っています。内側のループが減数ループになっている点に注目してください。このプログラムは配列arを変えながら動くのですが、ループの中でar.[w - wk]を参照しているため、後ろから値を変えていかないとまずいのです。このあたりのことについては、上記の本と二つのサイトを読んでじっくり考えてもらえばわかると思います。

　ループの中は、max3fを呼び出し、参つの値の最大値を取りつつ、最後の数が一番大きかった場合だけ商品購入配列gを更新しています。

　最後にar,gで計算結果を返しています。ちょっと信じがたいですがこれで結果が得られるのです。

　再帰関数ppはdpの結果として得られた二つの配列から、購入すべき商品の一覧を抜き出して出力する関数です。

　最後のsolveは、dpを呼び出してppに渡すだけの関数です。