最初に
この投稿は 動的計画法（DP）の漸化式を基礎から理解-Frog 1の続編になります。Frog 1は1次元のDP問題でした。今回は2次元のDP、おそらくDP初心者にとって最初の難関となるナップザック問題について説明します。
前回と同じく再帰、もしくはメモ化再帰は取り扱いません。競技プログラミングでは漸化しでないと、TLEもしくはメモリエラーになることが多いためです。
問題
蟻本 P51より
重さと価値がそれぞれW(i)とV(i)であるようなら、n個の品物があります。これらの品物から、重さの総和がWを超えないようにえらんだときの価値の総和の最大値を求めなさい。
入力
n=4
(w,v) = ((2,3), (1,2), (3,4), (2,2))
貰うDP
貰うDPの漸化式はP55に記載されています。こちらを順番に説明していきます。
DPテーブルの説明
DPテーブルは縦軸がナップザックに入っている品物の数、横軸がナップザックに入っている品物の重さになります。項目は価値です。この項目を最大化することが目的となります。
初期値の設定
まずは初期値を設定します。今回は２次元のために初期値は２つの軸に分かれます。
- 品物数=0の時に価値は必ず0になります。
- 重さ=0の場合には品物はないために、価値は必ず0となります。
一つ目の品物ついて更新する。
ひとつめの重さ=2, 価値=3となります。横軸の1について順番に更新します。
まずナップザックの重さ=1の場合には、品物の重さより小さいために入れることができません。よって重さ、価値ともに変化はありませんので、ここは0となります。
次にナップザックの重さ=2です。今回は選択肢とては1) 品物を入れるか、2)品物を入れないかの２つがあります。この２つの選択肢について価値を比べて大きいほうを選びます。品物1の価値は3ですので、価値=3となります。
以下同様にして品物1を更新します。重さの制限は増えます。しかし品物1は重さ=2、価値=3で固定されているために価値は3となります。
品物2～4について同様に更新する。
品物2～4についても同様に更新します。ポイントとしては選択肢は２つ、一つはその行の品物を入れる、もう一つは何もしないということです。
最後の品物まで更新すると答えは7となりました。
まとめ
配るDP
貰うDPの漸化式はP56に記載されています。こちらを順番に説明していきます。
一つ目の品物ついて更新する。
初期値までは貰うDPと同じですので省略します。(0,0)が価値を配ることができるのは、(0,1)もしくは(2,1)の項目になります。
順番に更新を繰り返す。すでに価値が更新されている場合には大きいほうを優先する。
品物2～4について同様に更新する。
更新を繰り返すと答えは7となる。貰うDPでも配るDPでも答えは一緒となる。
まとめ
