ナップサック問題
for i ← 1 {\displaystyle i\leftarrow 1} to n do V [ i , 0 ] ← 0 {\displaystyle V[i,0]\leftarrow 0} end for
for i ← 1 {\displaystyle i\leftarrow 1} to n do
for w ← 0 {\displaystyle w\leftarrow 0} to W {\displaystyle W} do
if w i > w {\displaystyle w_{i}>w} then V [ i , w ] ← V [ i − 1 , w ] {\displaystyle V[i,w]\leftarrow V[i-1,w]}
else V [ i , w ] ← max ( V [ i − 1 , w ] , V [ i − 1 , w − w i ] + v i ) {\displaystyle V[i,w]\leftarrow \max(V[i-1,w],V[i-1,w-w_{i}]+v_{i})}
end if
end for
end for
Groovy でトップダウンの動的計画法(メモ化再帰)を使ったコードは以下の通り。
ナップサック問題において x i ∈ N {\displaystyle x_{i}\in \mathbb {N} } という制約を x i ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} と制限した問題を 0-1 ナップサック問題 という。元のナップサック問題では重量の合計がW以下であれば各品物はいくつでも入れることができたが、この問題の場合は1つまでである。
問題は次のように書かれる。
max ∑ i ∈ I v i x i s . t . ∑ i ∈ I w i x i ≤ W x i ∈ { 0 , 1 } ( ∀ i ∈ I ) {\displaystyle {\begin{array}{lll}\max &\sum _{i\in I}v_{i}x_{i}&\\\mathrm {s.t.} &\sum _{i\in I}w_{i}x_{i}\leq W&\\&x_{i}\in \{0,1\}&(\forall i\in I)\end{array}}}