ナップサック問題とは

ある容量Cのナップサックと，n個の品物が与えられたとする．n個の品物は，それぞれ異なる容量C_iと価値p_iだとする．このとき，ナップサックの容量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が返した組の中の最大価値と，その場合の要素の組を返します．

最後に，上記で示した記事の例を計算した結果を示します．