DPのメモ
個人的なDPのメモ。
DPでだいたい最後にdp[0][K]みたいな感じで、0 添字で参照してるので、これをdp[N][K]みたいに書けるようする。というのが目的。
単純なナップザックの問題だと、dpテーブルの添字が何を表しているのか、読み取りづらい。結果的に、漸化式を作るときに混乱しがち。これを回避するために、今一度、再帰から考える。
はじめに、蟻本にも載ってるナップザックの再帰関数。
def rec1(pos, W): if pos == N: return 0 ans = rec1(pos+1, W) if W-w[pos] >= 0: ans = max(ans, rec1(pos+1, W-w[pos])+v[pos]) return ans
これは最終的に、rec1(0, K)
みたいに呼び出すことによって、解を得ている。意味としては、0 から N-1 までの荷物から最大価値を計算する
というようになっている。しかも、実質、rec(N-1, ...)
から呼び出されているので、わかりにくい。
そして、これをrec2(N, K)
のように呼び出したいとして、書き直してみる。
def rec2(pos, W): if pos == 0: return 0 ans = rec2(pos-1, W) if W-w[pos-1] >= 0: ans = max(ans, rec2(pos-1, W-w[pos-1])+v[pos-1]) return ans
こんな感じになる。これで、rec2(N, K)
として同じ解を得ることができる。比較してみると、配列(リスト)を参照する数字が微妙に違ってくることがわかる。
この関数の意味としては、0 から N-1 までの荷物から最大価値を計算する
で上記と同じだが、N
という変わり得る情報が、呼び出しのときに残っているのでわかりやすいと思う(個人の見解)。
DPテーブルを追う時も、i が上がっていく方が考えやすいと思うし、積極的に、下の方の再帰をもとにして、DPを組み立てていきたい。そういうところを実感した点で、自分で書いて文字で説明するかいはあったかなと思う。