動的計画法によるナップザック問題を見た目で理解する 

# DPって分かりづらい...
そう思っている方、少なからずいらっしゃると思います。
私もその一人でした。

趣味プログラマな私は日ごろ各サイトのスキルチェック問題に挑み遊んでいるわけですが、上位の問題になってくると必ずといって良いほど出てくるナップザック問題。

ネットで調べても出てくるのはDP(動的計画法)を使用するということと、謎の数式とか良く分からない二次元テーブル。

分かってしまえば簡単なのですが、初心者には 

 .。o(何でこんなテーブルでナップザック問題が解けるんだ...?!)

となるわけです。
そもそもあのテーブルは何なんだ？

そんなわけで、初心者が初心者のために、あのテーブルが何なのかを説明します。
# 注意事項
筆者は初心者趣味プログラマで専門的な知識はあんまり無いです。
よって感覚で理解できそうな説明しかしません。
業界用語とかも良く分かりません。
もし間違っていることがあれば注意していただけると幸いです。

# ナップザック問題の前に
まずはこんな問題を解きます。
![rapture_20220806141217.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/f46e137d-0c6c-fb70-d21d-df30acfd6ff6.jpeg)
> あるスタート地点から各地点へのお散歩ルートがあります。
> この時、ちょうど10kmでA地点へ帰ってこれるルートが有るかどうか答えましょう。

## さぁ、全探索してみよう。
~~この問題の場合、どう考えてもA(2km) * 5 で10kmなんですが、精巧な問題作るのめんどくさいんで勘弁してください。~~

さて、動的計画法の基本は全探索です。
まずは全探索して木にして見ます。

木にするために、まずは各地点から次に移動できる地点と距離を列挙してみます。
![rapture_20220806141222.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/5e1acb7d-72bb-4cdd-6f0e-774c76443889.jpeg)

そして、コレを元に木を作ってみると以下のようになります。
各節に書かれているのは、**現在いる地点**と**スタート地点からの総距離**です。

![rapture_20220806141235.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/e8717eb0-88ce-58b1-f9a8-a009c20a4810.jpeg)

この木を効率よく全探索するには、木の中で **ある節以降、結果が同じになる枝はまとめてしまう** という事をします。
その節を見つけるためにはどうすればよいか？
それを調べるために、乱雑な木を距離で整列してみましょう。

![rapture_20220806141244.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/e0d83fef-4212-40e8-4924-fee7d6bb6f1c.jpeg)

なにか気づきましたか？
並べてみてみると、9km地点で同じ地点が複数出てますよね？
ある地点から次に移動できる地点は **現在いる地点に依存** します。
つまり、**どの地点から来ようが次の移動先は同じ** なわけです。

そのため、この重複した地点は纏めることができます。

![rapture_20220806141245.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/7aba1386-e8d5-62c0-1108-0c6c0da74603.jpeg)

さて、それでは纏められる枝を纏めてしまいましょう。

![rapture_20220806141257.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/181ef293-34d2-115c-456b-0c4d831dc622.jpeg)

移動先の枝が重なって見づらいですが、なんだかすごいすっきりしましたね。
すっきりついでに、この木を地点順に整頓してみましょう。

![rapture_20220806141306.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/2d688f83-287d-bbd5-8fd1-3d42b8f96f71.jpeg)

~~相変わらず枝でごちゃついてますが~~ なんだか見覚えのある形になっていませんか？
そう！動的計画法の説明でよく見るあのテーブルです！
動的計画法ではこの様に、**テーブルを使って結果が同じになる基点をメモする**わけです。

ちなみに、勘の良い方ならこの時点で「さっきの枝纏めるときに、最大化とか最小化とかすれば...」と察するわけですが。
筆者はそんな勘の良い人間では無いのでこのまま説明を進めます。

## 実際にテーブルでDPしてみよう。
さて、それでは以上の木から作られたテーブルを実際にDPテーブルでやって見ましょう。
まずやるべきことは地点数(5) * 距離軸(開始地点+目標地点 = 11)のテーブルを作成します。
状況により各セルの初期値は変わりますが、今回は有るか無いかだけが知りたいので0で初期化します。

![rapture_20220809215313.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/4ecb0e1e-2e19-ab44-96ce-8e8720594d0e.jpeg)

そして、開始地点が存在しますので、セル座標`(A , 0) = 1` とします。

![rapture_20220809215547.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/bd4f7566-ad02-4e5d-2cb0-3e547e15e797.jpeg)

ここからは、DPテーブルを左上から右下に向かって。
つまり
`(A , 0)` -> `(B , 0)` -> `(C , 0)` -> `(D , 0)` -> `(E , 0)` -> 
`(A , 1)` -> `(B , 1)` -> `(C , 1)` -> `(D , 1)` -> `(E , 1)` -> 
...
`(A ,10)` -> `(B ,10)` -> `(C ,10)` -> `(D ,10)` -> `(E ,10)`

という順番で各セルを読んでいきます。

やることは単純で、
**セルが0では無い場合、その地点からの移動先(次の地点 , 現在のy座標+移動量)のセルに1を加算する**
だけです。

それではやっていきましょう。
***

まずは、開始地点です。
`(A , 0) !== 0`ですので`(A , 0+2)` と `(B , 0+3)` に1を加算します。
![rapture_20220809215635.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/2d2ca36c-a2da-8f2b-b5df-911753d2a327.jpeg)

次のセル以降を読んでいきますが、次に0以外の値を持つセルは`(A , 2)`なので、そこまではただセルを読み飛ばすだけです。
![rapture_20220809215728.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/7ab7bd81-a3f2-478c-abbf-9c2db5a7ab07.jpeg)
 
次は`(A , 2) !== 0`なので`(A , 2+2)` と `(B , 2+3)` に1を加算します。
![rapture_20220809215756.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/34235efa-7ad7-2112-4de2-42ad02406073.jpeg)

次に何かするのは`(B , 3) !== 0`なので`(C , 3+1)` に1を加算します。
![rapture_20220809215843.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/78328383-a77e-b16b-1acb-463a22c9ad86.jpeg)

もう何回もやってますので`(A , 4) !== 0`は省略して、次は`(C , 4) !== 0`です。
`(D , 4+2)` と `(E , 4+1)` に1を加算します。
![rapture_20220809220019.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/ba409d17-3847-fe14-40ae-f2034a88133b.jpeg)

こんな感じでどんどんセルを読んでいき`(E , 7) !== 0`。
`(A , 7+2)` と `(B , 7+1)` に1を加算します。
![rapture_20220809220054.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/a9fadd0c-d59f-1c94-5717-c8b8cc58edaa.jpeg)

ここでついに`(A , 9)`で枝がまとまりました。
さらにセルを読み進めていくと、テーブル外に出る値が出てきます。
`(A , 8) !== 0`では`(A , 8+2)` と `(B , 8+3)` に1を加算しますが、`(B , 8+3 = 11)`はテーブル外なので、無視します。
![rapture_20220809220253.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/a8cf7acb-dd31-6d53-fc05-bdbc3284b308.jpeg)

と、そんな感じで全てのセルを読み終えた後、最後に問題の答えを読み取ります。
今回求めている答えは

> この時、ちょうど10kmでA地点へ帰ってこれるルートが有るかどうか答えましょう。

でした。

つまり、**(A,10)のセルが0でなければちょうど10kmでA地点へ帰ってこれるルートが有る**ということです。
![rapture_20220809220324.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/08642ac2-6c72-4d03-de6e-33ae1d952022.jpeg)

`(A,10) !== 0`ですので、答えはYESです。

## 消えてしまう情報
ここで一つ注意なのですが、上記の(A,10)の値が3なので、
「そうか!10km地点に到達するルートの組み合わせは全部で3つなのか!」
と思う方がいるかもしれませんが**それは間違い**です、

実際にはこの問題の範囲内では確かにゴールに到達するルートは3つなのですが、ここの3という数字はゴールまでのルート数ではなく**ゴールに到達する地点数**です。
10kmのA地点には3地点から到達できるという事を示しているだけで、途中のわき道情報は**枝がまとまった時点で上書きされてどれか一つしか残せません**。
今回はたまたま、到達するルートにわき道がなかっただけです。
わき道の情報も含めて、ゴールに到達する全てのルートの組み合わせ数が必要な場合は、セルから渡す動作を、1加算ではなく**セルの値を加算**にします。
![rapture_20220809230244.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/25a97d6b-79bb-3fa5-cab9-df59bfd29bc2.jpeg)

このテーブルを見ると10km地点のBとCに到達できるルートにわき道があったのですが、枝が纏められてわき道が消えていることが分かります。

## さて、最大化と最小化だ。
それでは、ここで最初の問題文を拡張します。

> あるスタート地点から各地点へのお散歩ルートがあります。
> この時、ちょうど10kmでA地点へ帰ってこれるルートのうち、取りうる最大の道の切り代わり数を答えましょう。
> ただし、同じ地点に戻る場合であっても道の切り替わりとして捉えます。(A -> A でも一回道が切り替わったとします。)

***
この問題を解くには、分岐のたびに数値を上げる。
つまり、次のセルに渡す数値を、**現在のセルの値 + 1**にします。

※開始地点での切り替え回数は切り替えていないから0なのですが、0だと有る無しの判断ができないので、開始地点を1として、最後に1引いて答えとします。


とりあえずはじめのほうだけやってみると、
![rapture_20220809230843.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/d740e95c-f20d-89a9-cc0a-1319e1aa2b09.jpeg)
![rapture_20220809230924.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/16f7b3c6-ad08-45dc-ac2a-262b5a7c30f3.jpeg)
という感じです。

さて、もうお分かりとは思いますが、
枝がまとまるときに、**より大きい値で上書きすれば最大値**
枝がまとまるときに、**より小さい値で上書きすれば最小値**
を得ることができます。
今回は**最大値**が知りたいので、上書き時はmax関数などを使用して大きいほうで上書きします。
ということで、各上書きセルのとこのみ画像を張りますと

![rapture_20220809231434.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/70da8bc2-ac02-db25-711c-de071078331a.jpeg)
![rapture_20220809231624.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/9377336b-44b2-e3ca-bfd7-58f5a55eca66.jpeg)
![rapture_20220809231751.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/47abd117-daa9-9eb1-6431-1afdcaa43b66.jpeg)
![rapture_20220809231854.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/297763b2-f47e-2530-deaa-9072843e4a5a.jpeg)
![rapture_20220809231906.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/121b4976-d0a8-4715-1b2f-c7609fa41396.jpeg)

これにより、10km先のA地点に到達するための最大の道切り替え回数は **8-1の7回** と求まりました。

## ルートも知りたい欲張りさんには
さて、どうせなら最大道切り替えルートの道順も知りたくないですか？
どうすればよいでしょうか？
この場合は、付属のデータを追加します。
追加するのは **どの地点から来たのか** を示す値です。
各セルの値を配列にし、`[前の地点座標 , 切り替え回数]` のセットで管理します。(前の地点は番号だけにして、逆算しても良いです)

ということで、途中経過はすっ飛ばして、テーブルを出すとこうなります。

![rapture_20220810000330.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/9cd459a6-c6a8-dcb2-f9f4-95de527ebbff.jpeg)

このテーブルから最大道切り替えルートは
**A -> B -> C -> E -> B -> C -> E -> A**
であることが分かりました。

# それじゃあ本題のナップザック問題
といっても、実はもう既にナップザック問題は解くことができます。
逆に言えば、**上記の問題と同じ形にして解いてしまう**ということです。

とりあえずは以下のような問題にします。
> 以下の品物を容量10の入れ物に入れたときの最大価値を答えましょう。
> A 重さ=1 価値=60
> B 重さ=3 価値=120
> C 重さ=4 価値=250
> D 重さ=5 価値=300
> E 重さ=8 価値=500
> ただし、各品物は0又は1つしか入れないものとする。(重複はしない)

さて。
一見すると、先ほどの問題と同じ解き方ができるように見えないかもしれません。
ですが、下の図を見てください。
![rapture_20220810002850.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/fac2770c-952b-f8fe-090d-f793c5f0f565.jpeg)
先ほどの散歩コースと似てません？
移動できる地点と重さを一覧にすると
![rapture_20220810004601.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/0339ddf6-44bc-00e6-23a3-38a6d43d3185.jpeg)
そっくりです。


つまりはAからスタートしてB->C->D->E->goalに到達する散歩コースの各地点を**遠回りするかしないか**で考え、**重さの制限は距離**で置き換えるわけです。

そして、セルに代入する値は、
遠回りした場合は**現在のセルの値 + 価値** 
遠回りしなかった場合は**現在のセルの値**
を代入するようにします。

それではやってみましょう。
***
今回はセルの初期値を-1にしておき、最初のセルは0にしておきます。
![rapture_20220810004943.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/445e7eb5-74e7-70dd-72a9-21dd37dab210.jpeg)
それでは、まず最初の品物Aですね。
`(A , 0) !== -1`なので、`(B , 0)`にはセルの値(0)をそのまま渡します。
`(B , 0+1)`にはセルの値+Aの価値(0+60)を渡します。
![rapture_20220810005039.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/d16be6e7-3e49-8f70-04b0-6d10ce299e7b.jpeg)
以下品物Eまでやっていくと
![rapture_20220810005430.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/dfff8921-786d-d916-ea4c-28d9c4b12f4f.jpeg)
こうなります。
この時点ではナップザックには品物Eだけが入ったときの情報が入ってますね。
それでは次の行に行きます。

`(B , 1) !== -1`なので、`(C , 1)`にはセルの値(60)をそのまま渡します。
`(C , 1+3)`にはセルの値+Bの価値(60+120)を渡します。

![rapture_20220810010459.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/a5e8c9c6-130c-aae9-36cd-3ba465d7ae20.jpeg)

そしてこの行も最後までやると
![rapture_20220810010522.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/f203f5c4-5809-b533-42de-9afee356e963.jpeg)

ここでナップザックの列には　
1. 何も入っていないとき
1. 品物Aだけが入っているとき
1. 品物Aと品物Eが入っているとき
1. 品物Eだけが入っているとき

という4つの情報が格納されています。

次の重さ2の行は-1の値しかないため無視して次の行をやっていきます。
![rapture_20220810011120.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/6701f611-9b42-7f63-5b1d-c4f978c39d0c.jpeg)
品物Eを足そうとしましたが、こちらは重さが11でテーブル外なので無視されました。

さらに進んでいくとD,4で最大化のセルが出ました。
![rapture_20220810011742.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/89864ac5-1b57-3d2f-dca7-17f60bdd8741.jpeg)
ここのセルは `品物A + 品物B` の価値と `品物C` の価値を比較していますね。
結果品物Cが勝ちましたので、ここで枝がまとまりました。

![rapture_20220810012226.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/906f7748-0d86-347d-ea24-49f7c3333dda.jpeg)
さらここでは `品物C + 品物D` の価値と `品物A + 品物E` の価値を比較していますね。
結果品物A + 品物Eが勝ちましたので、ここでも枝がまとまりました。

で、最終的には
![rapture_20220810012237.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2778968/f414c498-59ef-ce9c-3b72-a32e5f085e10.jpeg)

となりました。
最後にknapsack列を全て読み取り、最も大きな値が答えになります。
**答えは560**です。

# まとめ
うまく説明できたか分かりませんが、DPは以外にやってることはシンプルです。
慣れてくると、問題文を見たときに、「あ。これDPでやったところだ！」ってなります。
筆者も、最初はわけわかめでしたがあるとき「こういうことか！」ってなるとそのシンプルさにあっけに取られました。
ぜひ、難しく考えずにシンプルに理解してみてください。

DPが分からないという方の力に少しでも慣れたのであれば光栄です。