クリスマスイブには、クリスマスの雰囲気のあるアルゴリズムであるナップサック問題のアルゴリズムについて話します。ここでは、クラシックアルゴリズムと貪欲アルゴリズムの 2 つの解決方法を紹介します。時間がないため、与えられた配列はすでにソートされていることに注意してください。貪欲アルゴリズムではソートが必要になるかもしれませんが、クラシックアルゴリズムでは 1 つずつ比較するため、ソートはあまり重要ではありません。おそらく、2 つのアルゴリズムの最終的な実行効果は同じです。デバッグするときは、私が提供したテスト配列を変更することを忘れないでください。今日は本当に忙しいので、貪欲アルゴリズムで使用するソートアルゴリズムは書いていませんが、将来のソートアルゴリズムの説明時に使用する予定です。メリークリスマス、皆さん。
ナップサック問題：現在、容量が PSIZE のナップサックと N 個のアイテムがあります。これらのアイテムをナップサックに入れる必要があります。特定の要件（例：サイズの順）に従ってアイテムをできるだけ多く入れるか、アイテムの重みの合計が最大になるようにする必要があります。
問題の説明が終わったので、以下にアルゴリズムを示します。C 言語での実装です。また、バックトラックや動的計画法のアルゴリズムも時間があれば書きます。今日は本当に忙しいので、皆さんは楽しみにしてください。
/* ナップサック問題のクラシックな解法と貪欲アルゴリズム
* code cg
* 2008 年 12 月 24 日
* デバッグ環境：TC、devC++
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 5 /* アイテムの数を定義 */
#define PSIZE 150 /* ナップサックのサイズを定義 */
long item [N] = {15, 40, 50, 60, 90}; /* アイテム配列の初期化、貪欲アルゴリズムではサイズがソートされている必要があります */
int freespace[N] = {0};
int classic () {/* クラシックなアルゴリズム */
long size = PSIZE;
long used = 0;
int i;
for(i = N - 1 ; i >= 0 ; i--){
if ((size - used) >= item [i]) {/* サイズが収まるかどうかをチェック */
used += item [i]; /* アイテムをナップサックに入れる（使用済みのサイズにアイテムのサイズを追加）*/
freespace[i] = 1;
}
else { /* サイズが大きすぎる */
freespace[i] = 0;
}
}/* for */
return 1;
}
int greedy () {/* 貪欲アルゴリズム */
int i;
long size = PSIZE;
long used = 0;
for (i = N - 1 ; i>= 0 ; i--) {/* 大きなアイテムから順に考える */
if ((used + item [i]) <= size) {/* 現在のアイテムを入れることができるかどうかをチェック */
freespace [i] = 1; /* 1 は入れることを表す */
used += item [i]; /* ナップサックの残り容量を減らす */
}
else {
freespace[i] = 0;
}
}/* for */
if (size == used) /* 結果を返す */
return 1;
else
return 0;
}
void main() {
int i; /* カウンター */
for(i = 0 ; i < N ; i++) {
if(i % 5 == 0 )
printf("n");
printf ("%10ld" , item [i]); /* 最初に元のデータを入力する */
}/* for */
printf("nClassicn");
if (classic () == 1) {/* クラシックなアルゴリズム */
printf("Result");
for(i = 0; i < N; i++) {
if(i % 5 == 0 )
printf("n");
printf ("%10ld" , freespace [i]); /* 結果を出力する */
}
}
printf("nGreedyn");
if (greedy () == 1) {/* 貪欲アルゴリズム */
printf("Result");
for(i = 0; i < N; i++) {
if(i % 5 == 0 )
printf("n");
printf ("%10ld" , freespace [i]); /* 結果を出力する */
}
}
}