スポンサーリンク
再帰を使った場合
容量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
動的計画法で漸化式を使った場合
最後に漸化式を使った場合です。
$ 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
スポンサーリンク
