9

動的プログラミングを使用して、Haskell でナップザックの問題を解決しています。私の最初の試みは、2 次元の表を作成することでした。しかし、入力が大きい場合 (例: 100 * 3190802 テーブル)、メモリは簡単に爆発します。

i指定された行は行のみに依存することを知っているので(i - 1)、代わりに末尾再帰を利用することを期待して関数を記述します。

import Data.Vector (Vector, (!))
import qualified Data.Vector as V

-- n items, k capacity, vs values, ws weights
ans:: Int -> Int -> Vector Int -> Vector Int -> Int
ans n k vs ws =
    let row = initRow k vs ws
    in  row ! k

initRow :: Int -> Vector Int -> Vector Int -> Vector Int
initRow k vs ws = itbl 1 $ V.replicate (k + 1) 0
    where n = V.length vs
          itbl i row
             | i > n = row
             | otherwise = itbl (i + 1) $ V.generate (k + 1) gen
             where gen w =
                       let w_i = ws ! (i - 1)
                           no_i = row ! w
                           ok_i = row ! (w - w_i) + (vs ! (i - 1))
                       in
                           if w < w_i then no_i
                           else max no_i ok_i

コードに示されているように、itblはそれ自体を再帰的に呼び出し、戻り値に対してそれ以上の計算は行われません。ただし、メモリは容赦なく増加しtopます。

 VIRT   PID USER      PR  NI  RES  SHR S  %CPU %MEM    TIME+  COMMAND
1214m  9878 root      20   0 424m 1028 S  40.8 85.6   0:16.80 ghc

コンパイラが末尾再帰用に最適化されたコードを生成するのを妨げるコードはありますか?

コード データ

--

4

1 に答える 1