ナップサック問題

ようやく動的計画法が少しわかってきた。

 


-- given
-- goods:（体積,価値)のリスト
-- capacity: 体積の総和の上限値
-- unknown
-- 体積の総和の上限値を超えない範囲で、
-- totalValue: （体積,価値）を組合せたときの価値の総和の最大値
-- selected : 価値の総和が最大になる（体積,価値）の組合せ


import Data.Array
goods :: [(Integer, Integer)] -- (volume, value)
goods = [(3,1), (4,2), (5,3)]


-- 容量制限 -> 価値の総和の最大値
calc :: Integer -> Integer
calc capacity = totalValue ! capacity -- 配列 totalValue の capacity 番目の要素が戻り値となる
where
totalValue = array (0, capacity) [(volume, maximum $ map
(\(w, v) -> if volume < w then 0 else totalValue ! (volume - w) + v)
goods) | volume <- [0..capacity]]

-- capacity: 容量上限値。 volume の総和 <= capacity の制約のもと、
-- totalValue :value の総和の最大値 を求める
main :: IO ()
main = do capacity <- readLn
print $ calc capacity

 Haskell の ! がなんの意味かわからなくて困った。配列の要素を参照する演算子らしい。

Prelude> import Data.Array
Prelude Data.Array> let a = array (1,5)[(i,i^2) | i <-[1..5]]
Prelude Data.Array> print a
array (1,5) [(1,1),(2,4),(3,9),(4,16),(5,25)]
Prelude Data.Array> print $ a ! 3
9

Haskell における配列の使い方 が為になった。

 

上記のコードだと、価値の最大値はわかるものの、その最大値となる品物の組合せがわからない。組合せを得るには、表を作ったあと、最大値となるつながりを逆にたどる必要がある。

病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ

逆にたどるには、マスを埋めるときにどのマスから来たのかを記録しておく必要がある。従って、マスは(価値の和, もとのマス）というタプルになるはず。

Data.Array は連想配列らしい。

第19回 配列でデータ・アクセスの効率を上げる | 日経クロステック（xTECH）

このように，Ixのクラスのインスタンスにはタプルも含まれます。このため，タプルを渡すことで，複数の値が組になった多次元の配列を表現できます。

 これを使えばよいはず。使い方を勉強しよう。