動的計画法part1(ナップザック問題)
問題概要
重さwと価値vがついた品物がn個ある。
これらの品物から、重さの総和がWを超えないように選んだときの
価値の総和の最大値を求めなさい。
問題解法
1.全探索
再帰的に、品物をチェックし入れた場合、入れなかった場合とで探索を繰り返す。
重さの総和が超えたり、すべての品物を探索し終えた場合に再帰終了とする。
▶︎指数時間かかってしまう。
2.メモ化
再帰的に呼び出す際、何度も同じ引数による関数呼び出しが発生する。
一度探索している状態については、あらかじめ配列等に結果を「メモ」しておき、
呼ばれるたびに、すでに探索済みか確認し、探索が終えていれば再帰を行わない。
3.動的計画法
漸化式を作ることで、再帰関数を使わないようにする。
漸化式は、nの状態は、n-1の状態から導きだすことができることを利用した式である。
ナップザック問題では、
\[ dp[n][j] = 0 \]
\[ dp[i][j] = dp[i+1][j] (j < w[i]) \]
\[ dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]) (それ以外) \]
(品物i番目以降の品物から重さの総和がj以下となるように選んだときの価値の総和)
という漸化式が得られる。
この式を利用し、i=Nから調べていけば、すべての状態の評価値を算出することができる。
回答案(C#)
class Knapsack { public int solveDP(int N, int[,]wv, int W){ int[,] dp= new int[N+1,W + 1]; for(int i = N-1; i >= 0; i--){ for(int j=0; j<= W; j++){ if (j < wv [i, 0]) { dp [i, j] = dp [i + 1, j]; }else{ dp [i, j] = max (dp [i + 1, j], dp [i + 1, j - wv [i, 0]] + wv [i, 1]); } } } return dp[0, W]; } public int max(int num1, int num2){ if (num1 > num2) { return num1; } else { return num2; } } }