この記事はRICORA Advent Calender 2022の12日目の記事になります。
はじめに
AtCoder Beginner ContestのD問題に取り組んでいたところ、解説で動的計画法(DP)を使うことが書かれていました。そこでこの動的計画法について、学んだことをまとめました。
今回
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
を参考にさせていただきました。
動的計画法とは
動的計画法とは数学の漸化式のように解く方法になります。例えば、
\left\{
\begin{array}{l}
x_{n+1}=3x_{n} \\
x_1=1
\end{array}
\right.
という漸化式は$x_1=1$だから$x_2=3$、$x_2=3$だから$x_3=9$…というように前の結果をもとにして結果を求めていきます。つまり、ひとつ前の結果をもとにして今の結果を求めるというようにして、問題を細かく分けた小さな問題の解から元の問題の解を求める方法になります。
ナップザック問題とは
それでは本題である、ナップザック問題に入ります。ナップザック問題とは次のような問題になります。
例として、N=3,W=3とし、品物を(重さ,価値)=(2,3),(1,4),(3,6)としたとき、解は品物(2,3)と(1,4)を選んだときの7となります。
動的計画法以外で求めるには
動的計画法以外でナップザック問題を解く方法としては全探索があります。先ほどの具体例を全探索を用いて求めると次のようになります。
| 品物 | (2,3) | (1,4) | (3,6) | 重さ | 価値 |
|---|---|---|---|---|---|
| × | × | × | 0 | 0 | |
| 〇 | × | × | 2 | 3 | |
| × | 〇 | × | 1 | 4 | |
| × | × | 〇 | 3 | 6 | |
| 〇 | 〇 | × | 3 | 7 | |
| 〇 | × | 〇 | 5 | 9 | |
| × | 〇 | 〇 | 4 | 10 | |
| 〇 | 〇 | 〇 | 6 | 13 |
それぞれの品物について選ぶとき〇、選ばないとき×を書くと、この表のように8通りのパターンがあります。そして、それぞれのときの重さと価値の合計は右2行のようになります。この中で、重さが3を超えないときの価値の最大は重さが3、価値が7であるときで、品物(2,3),(1,4)を選んだときになります。
しかし、この方法では品物の数Nに対して、$2^N$通りのパターンが存在するため、N=100ほどの大きさでも時間がかかりすぎてしまいます。
具体例を動的計画法を使って解く
それでは、先ほどの具体例を動的計画法を使って求めます。まず、漸化式$x$には求めたいものである価値の最大値を入れることにします。動的計画法の考え方として、一度に全体の品物について考えるとわからなくなってしまうため、考える品物を一つずつ増やしていくということをします。これが問題を細かく分けることにあたります。このようにすることで、新しく選ぶ候補に入った品物についてのみ、選ぶか選ばないかを決めればよいということになります。そこで、添え字$i$をつけ、この$i$はi番目の品物までを考えるということを表しているとします。すると、$x_i$はi番目までの品物を考えたときの価値の最大値になります。
ただ、このままでは重さについての情報を持たないため、ひとつ前の値から求めることができません。そこで、添え字をもう一つ増やし、その添え字に重さを情報を持たせるということをします。新しく添え字$w$を追加し、重さがw以下であるということを表すとします。したがって、$x_{i,w}$はi番目までの品物を考えて重さがw以下であるときの価値の最大値になります。
次に、この$x_{i,w}$を用いて以下の表を考えます。
| i\w | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | ||||
| 1 | ||||
| 2 | ||||
| 3 |
この表の中には$x_{i,w}$の値が入ります。例えば、i=2,w=1には$x_{2,1}$の値が入ります。この表で、i=3,w=3のときの値$x_{3,3}$は「3番目までの品物を考えて重さが3以下であるときの価値の最大値」を表していることになります。これは、「すべての品物を考えて重さが3以下のときの価値の最大値」と同じであり、問題で問われているものと同じになります。そのため、この表の一番右下が答えであるということになります。
最初に、i=0の行を埋めます。i=0のとき「0番目までの品物で考える」ということになり、品物を一つも選ぶことができないため、すべて0とします。
| i\w | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | ||||
| 2 | ||||
| 3 |
続いて、i=1の行を埋めます。各マスに入る数の候補としては次の2つがあります。
- 一つ上の行の数（一番目の品物である(2,3)を選ばない）
- 一つ上の行の2列左にある数に3を足した数（一番目の品物である(2,3)を選ぶ）
候補2について、2列左にある数の重さに重さ2を加えたとしても、その列の重さ以下となり、重さがその列の重さを超えることはないため、その数に新たな価値3を加えた数も候補となります。例えば、w=3を埋めるとき、2列左の数は重さが1以下であるため、その重さに2を足しても3以下となり、w=3の条件を満たすため$x_{1,1}+3$は数の候補となります。
また、候補2は、2列左の列が存在しないとき選ぶことはできないため、実際に入る数としては次の2通りになります。
- 候補1（2列左の列が存在しないとき）
- 候補1と候補2のうち大きい方（2列左の列が存在するとき）
これをもとにして埋めると、w=0,1のときは2列左の列が存在しないため候補1でいずれも0、w=2,3のときは2列左の列が存在するため候補1と候補2のうち大きい方となり、いずれも候補1が0、候補2が0+3であるため3になります。
| i\w | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 |
| 2 | ||||
| 3 |
次に、i=2行を埋めます。i=1のときと同じように、候補は
- 一つ上の行の数（二番目の品物である(1,4)を選ばない）
- 一つ上の行の1列左にある数に4を足した数（二番目の品物である(1,4)を選ぶ）
となり、実際に入る数は、
- 候補1（1列左の列が存在しないとき）
- 候補1と候補2のうち大きい方（1列左の列が存在するとき）
となります。よって、wの値と候補1、候補2の数、実際に入る数は次のようになります。
| w | 候補1 | 候補2 | 実際に入る数 |
|---|---|---|---|
| 0 | 0 | × | 0 |
| 1 | 0 | 0+4 | 4 |
| 2 | 3 | 0+4 | 4 |
| 3 | 3 | 3+4 | 7 |
| i\w | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 |
| 2 | 0 | 4 | 4 | 7 |
| 3 |
最後に、i=3行を埋めます。同様にして、候補は
- 一つ上の行の数（三番目の品物である(3,6)を選ばない）
- 一つ上の行の3列左にある数に6を足した数（三番目の品物である(3,6)を選ぶ）
となり、実際に入る数は、
- 候補1（3列左の列が存在しないとき）
- 候補1と候補2のうち大きい方（3列左の列が存在するとき）
となります。よって、wの値と候補1、候補2の数、実際に入る数は次のようになります。
| w | 候補1 | 候補2 | 実際に入る数 |
|---|---|---|---|
| 0 | 0 | × | 0 |
| 1 | 4 | × | 4 |
| 2 | 4 | × | 4 |
| 3 | 7 | 0+6 | 7 |
| i\w | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 |
| 2 | 0 | 4 | 4 | 7 |
| 3 | 0 | 4 | 4 | 7 |
これで、表をすべて埋めることができました。最初にも、述べたように一番右下の数が答えとなるため、答えは7となります。
一般化しよう
前で具体例を用いて考えたことを一般化します。手順は次のようになります。
- 漸化式の添え字を決める
- 漸化式を決定する
- 初期値を決定する
1. 漸化式の添え字を決める
具体例の最初で述べたように、添え字の数は2つで、ひとつは何番目までの品物を考えるか、ひとつは重さは何以下であるかというようにします。
2. 漸化式を決定する
i番目の品物の価値を$v_i$、重さを$w_i$とすると、候補は
- 一つ上の行の数（$i$番目の品物である($v_i$,$w_i$)を選ばない）
- 一つ上の行の列$v_i$左にある数に$w_i$を足した数（$i$番目の品物である($v_i$,$w_i$)を選ぶ）
となり、実際に入る数は、
- 候補1（$v_i$列左の列が存在しないとき）
- 候補1と候補2のうち大きい方（$v_i$列左の列が存在するとき）
となります。いま、i=$i$、w=$w$のマスを埋める、つまり$x_{i,w}$の値を求めるとすると$v_i$列左の列が存在しないとき$w-w_i<0$であり候補1の値は$x_{i-1,w}$、$v_i$列左の列が存在するとき$w-w_i\geq0$であり候補1と候補2のうち大きい方の値は$max(x_{i-1,w},x_{i-1,w-w_i}+v_i)$となります。これらをまとめると漸化式は
x_{i,w}=
\left\{
\begin{array}{ll}
x_{i-1,w} & (w<w_i)\\
max(x_{i-1,w},x_{i-1,w-w_i}+v_i) & (w \geq w_i)
\end{array}
\right.
となります。
3. 初期値を決定する
初期値は、具体例の表を埋めるときに最初に行ったi=0の行を0で埋めたことがあたるため、
x_{0,w}=0{\;}(w=0,1,2,…,W)
になります。
まとめ
以上より漸化式は
x_{i,w}=
\left\{
\begin{array}{ll}
x_{i-1,w} & (w<w_i)\\
max(x_{i-1,w},x_{i-1,w-w_i}+v_i) & (w \geq w_i)
\end{array}
\right.\\
x_{0,w}=0{\;}(w=0,1,2,…,W)
となります。
計算量
動的計画法を用いた方法では、表のマスの数と同程度の計算量が必要になるため、$O(NW)$となります。
最後に
今回は、動的計画法について、ナップザック問題を通して学んだことをまとめました。参考にさせていただいた記事では、ナップザック問題のほかにもたくさんの問題を取り扱っているため、そちらにも取り組んでいきたいです。