スポンサーリンク

再帰を使った場合

参考:[c言語]フィボナッチ数列を動的計画法でコーディング

容量Wmaxのナップザックに、N個の品物を入れる。
品物iの重さがw[i] 価値がv[i]であるときに、容量Wmaxを超えない、
かつ、価値が最大となるように品物を選択してナップザックに詰める。
その時の価値を求めます。

まずは、再帰を使った全探索の方法です。

下記がサンプルコードになります。

$ cat sample.c 
#include <stdio.h>
#include <time.h>


//ナップザックは容量Wmax(引数で設定)
//v[i] w[i]の品物がN個
//(1<= i <= N)

#define N (6)

int w[N] = {1, 4, 7, 2, 7, 2};
int v[N] = {5, 2, 6, 2, 7, 4};

int getNapVal(int i, int Wmax){
	int ret1, ret2;
	
	//printf("getNapVal i=%d Wmax=%d\n", i, Wmax);
	if(i == N){
		return 0;
	}else if(w[i] > Wmax){
		return getNapVal(i + 1, Wmax);
	}else{
		ret1 = getNapVal(i + 1, Wmax);
		ret2 = getNapVal(i + 1, Wmax - w[i]) + v[i];
		return (ret1 > ret2) ? ret1 : ret2;
	}
}

int main(){
	printf("%d\n", getNapVal(0, 0));
	printf("%d\n", getNapVal(0, 3));
	printf("%d\n", getNapVal(0, 7));
	printf("%d\n", getNapVal(0, 35));
		
	return 0;
}

ポイントは下記の部分ですね。

	//品物iをNまで探索したら0を返す
	if(i == N){
		return 0;
	//品物iが容量オーバーでナップザックに詰めることができなければ
	}else if(w[i] > Wmax){
		//品物iを詰めずに次の品物(i + 1)を検討
		return getNapVal(i + 1, Wmax);
	//品物iがまだナップザックに詰めることができれば
	}else{
		//品物iを詰めない場合と
		ret1 = getNapVal(i + 1, Wmax);
		//品物iを詰めた場合を計算して、
		ret2 = getNapVal(i + 1, Wmax - w[i]) + v[i];//残りの容量がw[i]だけ減って、価値がv[i]だけプラスされる
		//価値が大きい方をreturnで返す
		return (ret1 > ret2) ? ret1 : ret2;
	}

下記が実行結果になります。

$ gcc -o sample sample.c 
$ ./sample 
0
9
11
26

スポンサーリンク

動的計画法のメモ化再帰を使った場合

次は、メモ化再帰の方法です。

$ cat sample2.c 
#include <stdio.h>
#include <time.h>


//ナップザックは容量Wmax(引数で設定)
//v[i] w[i]の品物がN個
//(1<= i <= N)

#define N (6)
#define WEI_MAX (100)

int memoData[N + 1][WEI_MAX + 1] = {};
int w[N] = {1, 4, 7, 2, 7, 2};
int v[N] = {5, 2, 6, 2, 7, 4};

int getNapVal(int i, int Wmax){
	int ret1, ret2;
	
	if(memoData[i][Wmax]){
		return memoData[i][Wmax];
	}
	
	//printf("getNapVal i=%d Wmax=%d\n", i, Wmax);
	if(i == N){
		return 0;
	}else if(w[i] > Wmax){
		return memoData[i][Wmax] = getNapVal(i + 1, Wmax);
	}else{
		ret1 = getNapVal(i + 1, Wmax);
		ret2 = getNapVal(i + 1, Wmax - w[i]) + v[i];
		return memoData[i][Wmax] = (ret1 > ret2) ? ret1 : ret2;
	}
}

int main(){
	printf("%d\n", getNapVal(0, 0));
	printf("%d\n", getNapVal(0, 3));
	printf("%d\n", getNapVal(0, 7));
	printf("%d\n", getNapVal(0, 35));
		
	return 0;
}

ポイントは下記の一度計算していたら、計算はスキップしてメモデータの値を返す箇所です。

	if(memoData[i][Wmax]){
		return memoData[i][Wmax];
	}

計算していなければ、計算してメモデータに結果を格納します。
	if(i == N){
		return 0;
	}else if(w[i] > Wmax){
		return memoData[i][Wmax] = getNapVal(i + 1, Wmax);
	}else{
		ret1 = getNapVal(i + 1, Wmax);
		ret2 = getNapVal(i + 1, Wmax - w[i]) + v[i];
		return memoData[i][Wmax] = (ret1 > ret2) ? ret1 : ret2;
	}
}

下記が実行結果になります。

$ gcc -o sample sample2.c 
$ ./sample 
0
9
11
26

動的計画法で漸化式を使った場合

参考:最大部分配列問題をc言語で実装してみる

最後に漸化式を使った場合です。

$ cat sample3.c 
#include <stdio.h>
#include <time.h>


//ナップザックは容量Wmax(引数で設定)
//v[i] w[i]の品物がN個
//(1<= i <= N)

#define N (6)
#define WEI_MAX (100)

int dpData[N + 1][WEI_MAX + 1] = {};
int itemW[N] = {1, 4, 7, 2, 7, 2};
int itemV[N] = {5, 2, 6, 2, 7, 4};

int getNapVal(int Wmax){
	int ret1, ret2;
	int i, w;
	
	for(i = 0; i < N; i++){
		dpData[0][i] = 0;
	}

	for(i = 0; i < N; i++){
		//printf("i=%d\n", i);
		for(w = 0; w <= Wmax; w++){
			//printf("w=%d\n", w);
			if(itemW[i] > w){
				dpData[i + 1][w] = dpData[i][w];
			}else{
				ret1 = dpData[i][w - itemW[i]] + itemV[i];
				ret2 = dpData[i][w];
				dpData[i + 1][w] = (ret1 > ret2 ? ret1 : ret2);
			}
		}
	}
	
	return dpData[N][Wmax];
}

int main(){
	printf("%d\n", getNapVal(0));
	printf("%d\n", getNapVal(3));
	printf("%d\n", getNapVal(7));
	printf("%d\n", getNapVal(35));
		
	return 0;
}

ポイントはほぼコード全てになりますが下記ですね。

	//品物i=0から順にi=Nまでループ処理する
	for(i = 0; i < N; i++){
		//printf("i=%d\n", i);
		//さらに、品物iに対して、ナップザックの残りの容量を0からWmaxで変化させて
		//容量が残りwの場合に価値の最大値を求める
		for(w = 0; w <= Wmax; w++){
			//printf("w=%d\n", w);
			//容量オーバーで、品物iをナップザックに詰めることができなければ
			if(itemW[i] > w){
				//品物iを詰めず
				dpData[i + 1][w] = dpData[i][w];
			//品物iが容量wの範囲内で、ナップザックに詰めることができれば
			}else{
				//品物iを詰めた場合と
				ret1 = dpData[i][w - itemW[i]] + itemV[i];
				//品物iを詰めない場合を計算して
				ret2 = dpData[i][w];
				//価値が大きい方を、dpData[i + 1][w]に格納
				dpData[i + 1][w] = (ret1 > ret2 ? ret1 : ret2);
			}
		}
	}

下記が実行結果になります。

$ gcc -o sample sample3.c 
$ ./sample 
0
9
11
26

スポンサーリンク