前回のポストを書いてて、これはDP(Dynamic Programming、動的計画法)を遅延評価で実現しているんじゃないか、ということをふと思いました。

それならばもっと難しいDPの問題も遅延評価を使って解いてみたら面白いんじゃないか、とふと思いました。

やってみました。

問題に選んだのはかの有名なナップザック問題です。

問題: 重さと価値をもったn個の荷物がある。合計Wの重さまで入るナップザックに荷物をいれるとき、ナップザックに入れる荷物の価値の合計が最大となる組み合わせをみつけよ。ただし、同一の荷物はいくつでも入れることができるとする。

個数制限なしのパターンのナップザック問題です。

漸化式DP(i, j)をi番目までの荷物を使って重量jまでナップザックに入れた時の価値の最大値、i番目の荷物の重量、価値をそれぞれw[i],v[i]とすると

DP(i, j) =
    DP(i-1, j) : (j > w[i] の場合)
    max( DP(i-1, j), DP(i, j-w[i]) + v[i] ) : (それ以外の場合)

このような漸化式をプログラムに反映します。

(defn dp-table [items]
  (letrec [tbl (lazy-cat [(repeat 0)]
                         (map (fn [t [w v]]
                                (letrec [js (map max t (lazy-cat (repeat w 0)
                                                                 (map + js (repeat v))))]
                                  js))
                              tbl items))]
    tbl))

(defn solve [items W]
    (nth (last (dp-table items)) W))

比較的シンプルなコードに収まりましたが正直分かりづらいですね。まあ素直にmemoize使って解けということでしょうか。

この問題を解くには2次元のテーブルが必要なので遅延シーケンスを2次元で作っています。

2行目のlazy-catで作っているのシーケンスがi番目までの荷物を使った場合の価値のリストです。 最初に[(repeat 0)]としているのは、0番目までの荷物を使った場合、つまり荷物をひとつも選べない場合はナップザックにどれだけの重量を入れられるとしても価値の最大値は0だからです。(このコードでは荷物は1番目から始まることにしているので0は何も選べない)

続く3行目のmapがこのコードのキモです。i方向のシーケンスのうち、今mapで処理しようとしているシーケンス(i番目)の一つ前のシーケンス(i-1番目)を変数tとして受け取り、i番目の荷物の重量、価値を変数w,vで受け取っています。そして、4行目のjsがi番目の(遅延)シーケンスとなります。

このjsですが、次のような考え方をします。上の漸化式を眺めてみてください。

i番目の価値シーケンスにおいて、0 <= j <= w[i]までの間のDP(i, j)は必ずDP(i-1, j)になります。この区間において(j > w[i])となることはありえないからです。(ちなみに、負の重量を考えると当然こうはなりませんが、今回は重量は正の整数ということにします)

つまり先の漸化式は次のように表せます。

DP(i, j) = DP(i-1, j) (0 <= j <= w[i]の場合)
DP(i, j) = max(DP(i-1, j), DP(i, j-w[i])) (j > w[i]の場合)

これをリストの形式に変換するため、次のシーケンスを考えましょう。

DP(i) : DP(i, 0)からDP(i, W)までの価値シーケンス
(0をw[i]回繰り返し) | (DP(i, 0)+v[i], DP(i, 1)+v[i], ..., DP(i, W)+v[i])

|はシーケンスの連結を表します。 この2つのシーケンスのそれぞれ対応する要素のmaxをとったものが、i番目のシーケンスということになります。プログラムと照らしあわせてみてください。

この解法の特徴は遅延シーケンスの特徴を活かして、Wの方向(jの方向)は無限に続くことが表現できていることでしょうか。

ということで晴れてDPテーブルが完成しました。あとはテーブルからデータを取り出すだけなので省略します。

拙い説明で伝わりづらかったとは思いますが、あくまで僕の作業メモということで。

おやすみなさい。