今日は簡単なアルゴリズムについて話します。最も単純なナップサック 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*/