ナップザック問題とは

難しい問題だが動的計画法を使うことで効率的に解けることで有名で、DPの紹介などでは定番の問題。

こちらの記事から、問題と漸化式を引用します。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～

$n$ 個の品物があり、$i$ 番目の品物のそれぞれ重さと価値が $\rm{weight}[i], \rm{value}[i]$ となっている ($i = 0, 1, ..., n-1$)。
これらの品物から重さの総和が $W$ を超えないように選んだときの、価値の総和の最大値を求めよ。

DPは、ある見方ではDAG上の最短距離/最長距離/パス数の数え上げであり、ある見方では漸化式の計算だ。以下の漸化式を計算すると、$n$個の品物$W$の重さの場合のナップザック問題を解くことができる。

＜DP漸化式＞

\rm{dp}[i+1][w] = \left\{
\begin{array}{ll}
\max (\rm{dp}[i][w-\rm{weight}[i]] + \rm{value}[i], \rm{dp}[i][w]) & (w \ge \rm{weight}[i]) \\
\rm{dp}[i][w] & (w < \rm{weight}[i])
\end{array}
\right.

<DP初期条件＞
$$\rm{dp}[0][w] = 0　(w = 0, 1, \dots, W)$$

漸化式を見ると、DPテーブルの$dp[i+1]$を求めるのにその直前の$dp[i]$しか使っていない。このような畳み込み処理は、foldrを使うことで簡単に実装することができる。

foldr

foldrは以下のような関数だ。f :: a -> b -> bを実装すると、それを使って畳み込んでくれる。

foldr :: (a -> b -> b) -> b -> [a] -> b

foldrでナップザックDP

まずfoldrの型変数a, bが何になるかを考える。

ナップザック問題は重さと価値のリストが入力として渡されるので、型変数aは(Int, Int)になるだろう。
また、DPテーブルのdp[i]は「i番目までの品物の中から、重さがそれぞれインデックスwを超えないように選んだときの、価値の総和の最大値のリスト」だ。すなわち、型変数bは「価値の総和の最大値のリスト」ということで、[Int]になるだろう。

これを当てはめて特殊化したfoldrの型は下の通りだ。

foldr :: ((Int, Int) -> [Int] -> [Int]) -- 畳み込み関数
      -> [Int]                          -- 初期値
      -> [(Int, Int)]                   -- 入力(W, V)
      -> [Int]

これで、作る畳み込み関数の型がknapsack :: (Int, Int) -> [Int] -> [Int]になることを確認できた。
このknapsackは、weight[i], value[i], dp[i]を受け取って、dp[i+1]を返す関数だ。

つまり、漸化式がそのまま畳み込み関数になる。

\rm{dp}[i+1][w] = \left\{
\begin{array}{ll}
\max (\rm{dp}[i][w-\rm{weight}[i]] + \rm{value}[i], \rm{dp}[i][w]) & (w \ge \rm{weight}[i]) \\
\rm{dp}[i][w] & (w < \rm{weight}[i])
\end{array}
\right.

実装に落とし込んでみると、読みやすくてなかなか良い。

knapsack :: (Int, Int) -> [Int] -> [Int]
knapsack (wi, vi) dp = do
    w' <- [0 .. length dp - 1]
    return $ if
        | w' >= wi  -> max ((dp !! (w' - wi)) + vi) (dp !! w')
        | otherwise -> dp !! w'

例題を解く

問題も同記事から引用する。何度も引用しているが、この記事はDPの入門に最適なので、DPについて不安がある人はこちらを読むと良い。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～

【数値例】
1)
　$n = 6$
　$(\rm{weight},\rm{value}) = {(2,3), (1,2), (3,6), (2,1), (1,3), (5,85)}$
　$W = 9$
　答え: 94 ((3,6), (1,3), (5,85) を選んだときが最大です)

これを解いてみよう。

>>> let w = 9
>>>     weights = [2,1,3,2,1,5]
>>>     values =  [3,2,6,1,3,85]
>>> foldr knapsack (replicate (w + 1) 0) (zip weights values)
[0,3,5,6,9,85,88,90,91,94]

replicate (w + 1) 0はDPテーブルの最初の行であり、dp[0]の値だ。重さ0から重さ9までを全て0で埋めたリストを初期値としている。返ってきたのはDPテーブルの最後の行であり、dp[n]の値だ。インデックス$W$には94が入っており、きちんと答えを出せていることを確認できた。

より複雑なDPに対応するには

ナップザック問題では、dp[i+1]を求めるのにdp[i]が分かっていればよかった。しかし、もっと過去の添字が必要だったり、DPテーブル全体が必要な場合はどうすれば良いのだろう。
残念ながらそれはfoldrでは対応できない。しかし、foldrの一般化であるCatamorphism（参考: おじいさん、今日のご飯はCatamorphismですよ）を過去の結果全てを畳み込み関数に渡すよう拡張したものがHistomorphismという名前で知られており、これを使えばDPテーブル全体を使って計算をすることができる。

Histomorphismについての解説もそのうち作る予定だが、ここで簡単にfoldrのHistomorphism版を紹介しよう。

Histomorphismでは、リストの代わりにリストに付加情報を持たせられるようにしたデータ構造を使う。余談だが、このデータ構造はリストのようにMonadのインスタンスにはならない。その代わり、Comonadのインスタンスになる。

data List' a b = Nil' b | Cons' b a (List' a b)
    deriving (Functor)

instance Comonad (ListA' a) where
    extract (Nil' b)      = b
    extract (Cons' b _ _) = b
    extend f l@(Nil' _)       = Nil'' $ f l
    extend f l@(Cons' _ x xs) = Cons' (f l) x $ extend f xs

histfoldr :: (b -> List' b a -> a) -> a -> [b] -> a
histfoldr f = histo . Nil'
    where
    histo hist []     = extract hist
    histo hist (x:xs) = histo (Cons' (f x hist) x hist) xs

foldrとは違い、histfoldrでは畳み込み関数が今までの計算のメモを受け取ることが分かる。これならDPテーブルのどの情報でも使うことができる。

まとめ

foldrを使ってナップザックDPを実装した。
また、histfoldrを使ってより一般的な畳み込み処理を行う方法を考えた。