今日はナップサック問題の最後の解法である再帰解法について話します。この解法は、現在のアルゴリズムの教材で基本的な解法の一つとして説明されています。もし、このようなアルゴリズムに関する本を持っている場合、ほとんどの場合、必要なアルゴリズムを見つけることができます。ナップサック問題の具体的な内容については、以前の記事を参照してください。関連リンクの下に直接アクセスできます。最近、私はナップサック問題の基本的な解法、動的計画法の解法、バックトラックの解法についての記事を公開しました。皆さんは私のページのリンクを参照してください。もし具体的な質問や理解できない点があれば、お気軽にコメントしてください。
では、再帰アルゴリズムについて説明します。私が提供するアルゴリズムは、有効な重量と最大利用可能価値を再帰パラメータとして使用し、各アイテムの重量と価値をテストして最適な結果を見つけるまで続けます。ただし、ここで設定した条件は、背負い物ができるだけ入るだけであり、貪欲アルゴリズムではないことに注意してください。
他の問題については、コードのコメントを読めば理解できると思います。もし理解できない部分があれば、お気軽にコメントしてください。最近、私は試験に忙しいため、忙しいかもしれませんが、ご了承ください。
以下はコードです：デバッグ環境：GCC、TC
/*
* ナップサック問題の再帰解法
* コード CG
*2008 年 12 月 30 日
*/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
#define N 5 /* 入力要素の数を制御 */
#define MAX 100 /* ナップサックの最大許容重量 */
int result;
int select[N],selectW[N];
struct{
int weight;
int price;
} items [N]; /* アイテムの構造体を定義 */
/*
*knapsacks () ナップサックの再帰アルゴリズム
* パラメータ：int i ナップサックに入れるアイテムの位置
int w 使用済みのナップサックの重量
int p 使用可能な最大価格
*/
void knapsacks (int i, int w, int p){/* ナップサックの再帰アルゴリズム */
int k;
if ((w + items [i].weight) < = MAX){ /* アイテム I の重量をナップサックに入れることができるかどうか */
selectW [i] = 1; /* 重量が許容される場合、一時的にナップサックに入れる */
if (i < N - 1){/*i < N-1?*/
knapsacks(i + 1, w + items[i].weight, p);
}
else{
for (k = 0; k < N ; k++){
select[k] = selectW[k];/*selectW -> select*/
}/*for*/
result = p;
}/*else*/
}/*if*/
if (p - items [i].price > result){/* アイテム i をナップサックに入れない場合、元に戻す */
selectW[i] = 0;
if (i < N - 1){
knapsacks(i + 1, w ,p - items[i].price);
}
else{
for(k = 0; k < N; k++){/*selectW -> select*/
select[k] = selectW[k];
}
result = p - items[i].price;
}/*else*/
}/*if*/
}/*knapsacks*/
int main(){
int i;
int w = 0,v = 0;
int sumPrice = 0; /* 入力カウンタ */
int maxWeight = MAX;
printf ("W と V を入力してください：w,vn");
for (i = 0; i < N ; i++){
scanf("%d,%d",&w,&v);
items[i].weight = w;
items[i].price = v;
printf("W = %d,P = %dn",items[i].weight, items[i].price);
selectW [i] = 0; /* レコード配列をクリア */
select[i] = 0;
sumPrice += v; /* 合計価格データを記録 */
}/*for*/
printf ("最大重量：% dn", maxWeight);
result = 0;
printf ("合計価格：% dn", sumPrice);
knapsacks (0, 0, sumPrice);/* ナップサック操作を開始 */
printf("| ID | WT | PR |n");
for (i = 0; i < N; i++){
if (select[i]){
printf("|%-4d|%-4d|%-4d|n",i+1,items[i].weight, items[i].price);
}
}/*for*/
printf ("結果：% dn", result);
system("PAUSE");
return 0;
}