Clojureでナップサック問題を動的計画法で解く
ナップサック問題とは
ある容量Cのナップサックと,n個の品物が与えられたとする.n個の品物は,それぞれ異なる容量Ciと価値piだとする.このとき,ナップサックの容量Cを超えない範囲で,品物の価値の総和を最大にする組み合わせを求める.
詳しくは,ナップサック問題 - Wikipedia を参照されたい.
デコード
今回は,同じ品物を一つまでしか入れられない場合を考える.
この場合の動的計画法の考え方は次のようになる.
- 容量の総和が 0 のときの,価値の総和を 0 とする.
- 品物 i を選択する
- すべての計算した容量の総和と価値の総和の組み合わせに対して,品物 i を加えた場合と、そうでない場合を考える.
- 容量の総和がナップサックの最大容量以下であり,すでに計算されたその容量での価値の総和よりも,現在考えている価値の総和の方が高い場合,価値の総和を更新する.
- すべての品物に対して2-4を繰り返す.
テキストだけでは分かりにくいと思うので,下記の記事を参考にして下さい.
最強最速アルゴリズマー養成講座:病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ
コード
ソースコード全体は,Gihub に公開している.
今回はClojureで実装したのだが,あんまり慣れていないのですごく汚い.
core.clj
(ns knapsack-problem.core) (use '[clojure.java.io]) (defn getItems [path del] "import items from filepath. path: filepaht, del: data delimiter" (let [lines (line-seq (reader path))] (map (fn [line] (map (fn [x] (read-string x)) (-> (.split line del) seq))) lines))) (defn dp [items limit] "solved knapsack problem using dp. items: (cost value), limit: cost limit" (def table {"0" 0}) (def backpointer {"0" (ref [])}) (doseq [item items] (def cached_backpointer backpointer) (doseq [cell table] (let [cost (str (+ (read-string (first cell)) (first item))) value (+ (last cell) (last item))] (if (<= (read-string cost) limit) (if (or (not (table cost)) (and (table cost) (< (table cost) value))) (do (if (or (not (backpointer cost)) (< (table cost) value)) (def backpointer (assoc backpointer cost (ref @(cached_backpointer (first cell)))))) (def table (assoc table cost value)) (dosync (alter (backpointer cost) conj item)))))))) [table backpointer]) (defn getMaxValueAndElement [items backpointer] "get mav value in. items: (cost value), backpointer: {cost: [items]}" (def m ["0" 0]) (doseq [item items] (if (< (last m) (last item)) (def m [(first item) (last item)])) ) [(last m) @(backpointer (first m))]) (defn -main [] "knapsack problem decoder" (let [table (dp (getItems "resources/input.csv" ",") 10)] (getMaxValueAndElement (first table) (last table))))
getItems は,ファイルから容量と価値の組をタプルで取り出します.
dp の部分で,先程紹介した動的計画法を用いてナップサック問題を解き,最終的な容量と価値の組とそこまでの経路を返します.
getMaxValueAndElement は,dpが返した組の中の最大価値と,その場合の要素の組を返します.
最後に,上記で示した記事の例を計算した結果を示します.
input.csv
3,2 4,3 1,2 2,3 3,6
result
[14 [(4 3) (1 2) (2 3) (3 6)]]