今日は簡単なアルゴリズムについて話します。最も簡単なナップサック 0 アルゴリズムで、再帰的方法を使用しています。コードを見た友達は、このコードがとても馴染み深いことに気づくでしょうが、CG がこれらのコードを提供する目的は、すべてのナップサックアルゴリズムを完全に提供することです。コードはとても簡単で、達人なら一目で理解できると思います。ここでのナップサックアルゴリズムは、物品の重さのみを考慮しており、物品の価値は考慮していません。再帰アルゴリズムを学ぶ初心者には必見のコードです。達人の方は復習としてご覧ください。CG は最近試験があり、一気に 6 科目を受ける必要があるため、ブログの更新がこれほど早くはありません。皆さんのご理解をお願いしますが、私は毎日少なくとも 1 本のブログ記事を書くペースを維持しますので、皆さんの応援をよろしくお願いします。明日のアルゴリズムブログ記事の予告をします。「バンカーアルゴリズム」です。今日はオペレーティングシステムを復習し、夜にシステムを再インストールしました。2 時間を無駄にしました。コードは明日デバッグしてお届けしますので、引き続きご注目ください。
/* 簡単なナップサック問題の再帰的解法
*code CG 2009-01-04
*/
#include"stdio.h"
#define N 6 /* アイテムの数 */
#define S 15 /* ナップサックのサイズ */
int W [N+1]={0,1,2,3,4,5,6};/* テストデータ、各アイテムの重さ、W [0] は使用しない */
/*knapsack () ナップサック関数
パラメータ int s 残りの重さ
int n 残りのアイテム数
戻り値 int ナップサックの割り当てが成功したかどうか
*/
int knapsack(int s,int n){
if (s == 0)/* 割り当て終了、成功 */
return 1;
if (s < 0 || (s> 0 && n < 1))/* 利用可能なスペースがない、またはアイテムの割り当てが完了 */
return 0;
if (knapsack (s - W [n] , n - 1)){/* 再帰 */
printf ("%-4d",W [n]); /* 出力 */
return 1;
}
return knapsack(s , n - 1);
}
int main()
{
if (knapsack (S , N))/* 再帰呼び出し */
printf("nOK!n");
else
printf("Failed!");
return 1;
}/*main*/