最近はアルゴリズムを勉強している。
なかなか頭に入ってこないので、アウトプットをして整理する。
なお、今回は設計技法「動的計画法」の話。
動的計画法は、Dynamic Programming。よくDPと言われる。
DPを一言で説明することは難しい。。。らしく、抽象的な説明しかできない。
「与えられた問題全体を一連の部分的問題に分解し、各部分問題に対する解をメモ化しながら、小さな部分問題からより大きな部分問題へと順に解を求めていく手法」とのこと。
つまり、問題全体を見て解くのではなく、部分的問題に分解して問題を少しづづ解いていくような手法ということ。（たぶん）
動的計画法を用いれば、以下のような問題を解くことが可能とのこと。
というわけで、ナップサック問題を考えてみる。
- ナップサック問題 N個の品物があり、i(=0,1,...N-1)番目の品物の重さは weight i, 価値は value jで与えられる。 このN個の品物から、重さの総和がWを超えないように、いくつか選ぶとする。選んだ品物の価値の総和として考えられる最大値を求めよ。（ただし、Wやweight iは0以上の整数とする）
動的計画法は、「部分的問題に分解して問題を少しづづ解いていくような手法」なので、どこが部分問題にできるのかを考える。
以下のような、ある程度の部分問題にすべきパターンがあるので、当てはめて考えてみる。
N個の対象物（0,1,2...,N-1）に関する問題に対して、最初のi個の対象物（0,1,2...i-1）に関する問題を部分問題として考える。
ナップザック問題に対して、上記パターンを当てはめると以下のようになる。
dp[i]（最初のi個）の品物（0,1,2...i-1）までの中から重さの総和がWを超えないように選んだ時の、価値の総和の最大値
しかし、これだと dp[i] から dp[i+1] をした時に、 i を選ぶか選ばないかの2通りの選択肢を検討することになるが、品物 i を加えることにしたときに、重さの合計がWを超えるかがわからない。
つまり、1次元配列では i を選ぶか選ばないかの2通り考える部分問題にならなくなり、詰まってしまう。
なので、以下のように変更する。
dp[i][j]（最初のi個）の品物（0,1,2...i-1）までの中から重さの総和がwを超えないように選んだ時の、価値の総和の最大値
これなら、2次元配列になり、重さと価値の表が完成する。
ためしに、 N=3, W=7 とする。値は {i, j} として、 {2, 9}, {5, 1}, {3, 10} とする。
一旦すべて i を選んでみると以下のような2次元配列が完成する。
// 0 1 2 3 4 5 6 7 ←W（w=0,1,2...W） // 0 [0 0 0 0 0 0 0 0] // 1 [0 0 9 9 9 9 9 9] // 2 [0 0 9 9 9 10 10 10] // 3 [0 0 9 19 19 20 20 20] // ↑N //
dp[0][j] の列は、何も品物を加えないということなので、すべての値が 0 となる。
dp[1][2] で価値 9 になったことがわかる。
dp[2][5] で価値 9 から 1 が加えられて 10 になったことがわかる。
dp[3][3] で価値 9 から 10 が加えられて 19 になったことがわかる。
その後、dp[3][5]で価値 19 から 1 が加えられて 20 になったことがわかる。
つまり、2次元配列になったことで、 i+1 される前の値は、 i からわかるような表になっていることがわかる。
これを整理すると、以下のようになる。
i番目の品物を選んだ後に {i+1, w} になるので、選ぶ前は {i, w-weight[i]} に価値（ value[i] ）を加算することでわかる。
つまり、i番目の品物を選ぶ場合は、 max(dp[i+1][w], dp[i][w - weight[i]) + value[i]) で最大値を更新。
i番目の品物を選ばないのであれば、 max(dp[i+1][w], dp[i][w]) で据え置く。
これをコードで書くと以下のようになる。
package main import ( "fmt" ) // - ナップサック問題 // N個の品物があり、i(=0,1,...N-1)番目の品物の重さは weight i, 価値は value jで与えられる。 // このN個の品物から、重さの総和がWを超えないように、いくつか選ぶとする。選んだ品物の価値の総和として考えられる最大値を求めよ。（ただし、Wやweight iは0以上の整数とする） func chmax(a *int, b int) { if *a < b { *a = b } } func main() { // 3 7 // 2 9 { w, v } // 5 1 // 3 10 var N, W int fmt.Scanf("%d", &N) fmt.Scanf("%d", &W) weight := make([]int, N) value := make([]int, N) for i := 0; i < N; i++ { fmt.Scanf("%d %d", &weight[i], &value[i]) } // [ 0 1 2 3 4 5 6 7<=W // 0 [0 0 0 0 0 0 0 0] // 1 [0 0 0 0 0 0 0 0] // 2 [0 0 0 0 0 0 0 0] // 3 [0 0 0 0 0 0 0 0] // N // ] var dp = make([][]int, N+1) for i := 0; i <= N; i++ { dp[i] = make([]int, W+1) } for i := 0; i < N; i++ { for w := 0; w <= W; w++ { // i 番目の品物を選ぶ場合 if w-weight[i] >= 0 { chmax(&dp[i+1][w], dp[i][w-weight[i]]+value[i]) } // i 番目の品物を選ばない場合 chmax(&dp[i+1][w], dp[i][w]) } } // [ 0 1 2 3 4 5 6 7<=W // 0 [0 0 0 0 0 0 0 0] // 1 [0 0 9 9 9 9 9 9] // 2 [0 0 9 9 9 9 9 10] // 3 [0 0 9 10 10 19 19 19] // N // ] fmt.Println("解答 =>", dp[N][W]) // 19 }
これで、ナップザック問題が解ける。
動的計画法は、むちゃくちゃ難しい。。。問題に対して、部分問題にどう落とし込むのか。が、かなり重要な気がした。
使いこなすまでに、相当な訓練が必要だと思う。
次は、二分探索法かな。。。
