12月26日 作業日誌 DP

こんばんは。

したいこと無限大な年末です。

DP

今日はDPの勉強をしていました。

動的計画法といって、あるものを求めたいときにそれまでの過程を全て求めることで早く計算できる、みたいな感じのものです。

わかりやすい例としてはフィボナッチ数列の計算があります。

例1.普通に計算する場合

1番目:1

2番目:1

3番目:1+1=2

4番目:1+(1+1)=3

5番目:(1+1)+(1+(1+1))=5

こんな感じになりますが

例2.DPを使う場合

準備:計算結果を格納する配列を用意する

それぞれの計算後、毎回結果を格納することで、過去の結果を再利用できる

1番目:1

2番目:1

3番目:1番目+2番目=2

4番目:2番目+3番目=3

5番目:3番目+4番目=5

例1の括弧で括っていた場所が、過去の計算結果に置き換わった形になります。

これはどちらかというとメモ化再帰？

まぁこんな感じなのですが、本題はここから。

ナップサック問題

容量と価値がそれぞれ設定されたn個の品物があります。それらの中から、ナップサックの容量wを超えないように品物を選ぶ時、最大の価値を求めよ。

という問題なのですが、これがなんとも難しいのです。

うまく言語化できないのでまだ自分の中で消化できていませんが、今日はこのナップサック問題の初級みたいなものを解説を見ながら勉強していました。

縦軸に品物、横軸に重さをとった表を埋めていくことで解けるのですが……。

これができるようになったら一段レベルアップする……かもしれませんね。

以上です。