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を組み立てていきたい。そういうところを実感した点で、自分で書いて文字で説明するかいはあったかなと思う。