読者です 読者をやめる 読者になる 読者になる

動的計画法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;
			}
		}

	
	}