ナップザックDP

無駄に同じ計算をしないように、ある条件下での計算結果を配列などに保存しておき、計算を高速化するためのアルゴリズム。

言葉で言ってもぴんとこないので例題で考えてみる。

フェボナッチ数列の計算

まず以下の問題で考えてみる。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja

フェボナッチ数列のある項を求める問題。

フェボナッチ数列は以下のように

fib(n) = fib(n−1) + fib(n−2)

ただし、fib(0) = 1, fib(1) = 1

と定義される。

単純に計算

これを普通に求めようとしてみる。

例えば n = 5 の項を求めようとすると、以下のように6回の計算をする必要がある。

fib(5) = fib(4) + fib(3)
- fib(4) = fib(3) + fib(2)
  - fib(3) = fib(2) + fib(1)
    - fib(2) = fib(1) + fib(0)
- fib(3) = fib(2) + fib(1)
  - fib(2) = fib(1) + fib(0)

しかし、fib(3)やfib(2)の計算が複数回されていて無駄がある。

fib(3)やfib(2)の計算は1度だけ行い、再利用すれば無駄な処理が減る。

配列に計算結果をメモする

無駄な計算を減らすために、配列に計算結果をメモする。

配列のindex=1にfib(1)を、index=2にfib(2)を...というように配列に計算結果を格納する。

コードで表現すると以下のようになる。

package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)

    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 1
    for i := 2; i < n+1; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }

    fmt.Println(dp[n])
}

こうすると、計算は fib(3), fib(4), fib(5)の3回しか行われず無駄な重複した計算が省ける。

これは厳密的には、メモ化再帰といい、DPの入口になっている。

次に典型問題のナップザックDPについて考える。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=ja

重さ制限があるナップザックに価値が最大になるようにアイテムを入れていく。

このような問題ではアイテムの個数を1個ずつ増やしていき、各状況で重さ制限を満たす価値の最大値を記録していく。

つまり考慮するアイテムの個数と重さ制限の重量をインデックスに取る2重配列に価値の最大値を記録する。

コードで表現すると以下のようになる。

package main

import (
    "fmt"
)

type item struct {
    v int
    w int
}

func main() {
    var N, W int
    fmt.Scan(&N, &W)
    items := make([]item, N+1) // indexと番目が一致するように標準入力を受け取る
    for i := 1; i < N+1; i++ {
        fmt.Scan(&items[i].v, &items[i].w)
    }

    dp := make([][]int, N+1) // 品物を0からN個使う場合それぞれでの価値の最大値を記録する二重配列
    for i := 0; i < N+1; i++ {
        dp[i] = make([]int, W+1)
    }

    for i := 1; i < N+1; i++ { // 品物を1個からN個使う場合それぞれを考える. 品物が0個のときは価値は0なのでスキップしてOK.
        item := items[i]
        for w := 0; w < W+1; w++ { // 制限が0からWまでの場合での価値の最大値を考える
            if item.w <= w {
                surplus := dp[i-1][w-item.w] // 余剰分の重さ制限での価値の最大値
                if item.v+surplus > dp[i-1][w] {
                    dp[i][w] = item.v + surplus
                } else {
                    dp[i][w] = dp[i-1][w]
                }
            } else {
                dp[i][w] = dp[i-1][w]
            }
        }
    }

    var max int
    for i := range dp[N] { // 全てのアイテムを考慮した場合の最大値を求める
        if max < dp[N][i] {
            max = dp[N][i]
        }
    }
    fmt.Println(max)
}

アイテムを1つずつ増やして、まずアイテムの重さが重さ制限を満たしていることが第1条件になる。

その上で、重さ制限が空いていれば新アイテムをただ追加する、容量が空いていなくても既存のアイテムを除いて新アイテムを追加した方が価値が最大になる可能性もある。

このように幾つかのパターンが考えられるが、新アイテムの重さから重さ制限までの重量で余剰している重さでの価値の最大値を考えて、新アイテムの価値と余剰分の最大値の和が既存の価値の最大値を上回れば更新することにすれば、アイテム追加のパターンを考える必要はない。

このようにして、DPでは配列にメモした計算結果を再利用して無駄な重複した計算を省いて処理を進めていく。