Arantium Maestum

プログラミング、囲碁、読書の話題

Clojureで動的計画法を使ってKnapsack Problemを解いてみる

Project Eulerの31問と同じような動的計画法を使ったナップサック問題の解き方

m kgまで入るカバンと、n個のモノがある。

モノiはx-i kgでy-i円の価値がある。

カバンに入り、価値の合計が最大になるモノの組み合わせは何か。

まずはデータ構造の定義。

(def empty-sack {:amount 0 :items []})

空のカバン。価値も0でモノも空のベクトル。

カバンの重さはカバンのプロパティにしない。後ほど関数の中で作る「場の状態」を表すknapsacksというカバンのリスト内の位置で重みを表す。

基本的に空要素を定義することでデータの形を決めている。本当はrecordなどを使ったほうがいいのだろうが、まだちゃんとrecordを理解仕切れていない。今度今までのコードを書き直してrecordで遊んでみよう。

次に、モノをカバンに追加する関数:

(defn add-to-sack [sack [_ i-amount :as item]]
  {:amount (+ (:amount sack) i-amount)
   :items (conj (:items sack) item)})

空じゃないカバンにしか追加しない関数:

(defn add-to-non-empty [sack item]
    (if (= sack empty-sack)
      sack
      (add-to-sack sack item)))

この(if (p x) x (f x))やその逆の構文って結構頻出するだろうから、より簡明な書き方がありそうな気もする。

組み合わせると最終的な関数ができる:

(defn solve-knapsack [items max-weight]
  (let [f (fn [knapsacks [weight _ :as item]]
            (->> knapsacks
                 (map #(add-to-non-empty % item))
                 (cons (add-to-sack empty-sack item))
                 (concat (repeat (dec weight) empty-sack))                         
                 (map (partial max-key :amount) knapsacks)))
        start-knapsacks (repeat max-weight empty-sack)]
    (apply max-key :amount 
      (reduce f start-knapsacks items))))

ちょっとややこしいので解説すると、fという酷い名前の関数内関数がキモになっている。

この関数は

引数が

  • i-1番目までのすべてのモノを使って出来る、各重量で最も合計価値の高いカバンのリスト。(カバンの重量 ー 1)がリスト内の位置になる。
  • i番目のモノ

戻り値が

  • i番目までのすべてのモノを使って出来る、各重量で最も合計価値の高いカバンのリスト

となっている。

構成要素の4つの部分の詳細としては:

(map #(add-to-non-empty % item))

空じゃないカバンにだけ、i番目のモノを追加していく。この段階でリスト内のインデックスとカバンの重量が合わなくなっているが、それは後のステップで修正する。

(cons (add-to-sack empty-sack item))

i番目のモノだけ入ったカバンをリストの頭に追加。元のリストに存在していない重量0の位置に追加されるので、重量の相対的な位置関係はあっている。ただし、全部が(i番目のモノの重量 ー 1)分だけずれている。

(concat (repeat (dec weight) empty-sack))

ここでインデックスを完全に修正。この時点で、i-1番目までのモノを使っての各重量の最善のカバンにi番目のモノを加えたリストが出来上がる。

(map (partial max-key :amount) knapsacks)))

各重量で、モノiを使ったカバンと使ってないカバンとで、各重量でより価値の高いものを選ぶ。これで、i番目までのすべてのモノを使っての最善な組み合わせになる。

あとはreduceで空のカバンばかりのリストをi=1...nまでのモノで順次更新していくだけ。

使い方:

(def items [[3 2] [4 3] [2 2] [9 20] [2 3] [3 6]])
(def max-weight 15)
(solve-knapsack items max-weight)

これだと答えが

{:amount 29, :items [[9 20] [2 3] [3 6]]}

になる。ちなみにこの答えの重量は14で、重量がぴったり15になる組み合わせよりも14になるもののほうが価値が高い、という点もちゃんと計算されている。