聖誕前夜講點比較具有聖誕感覺的演算法，背包問題演算法，這裡我寫了經典算法和貪心算法兩種解決方法，因為時間不多，所以給出的陣列是已經排序的，因為貪心算法可能要用得到，經典算法因為是一個一個比較，因此排序也就沒有那麼重要了，可能兩種演算法的最終運行效果一樣的，朋友們調試的時候記得修改我給出的測試陣列，今天實在太忙了，貪心使用的排序演算法沒有寫，留著以後給大家講排序演算法的時候使用吧，聖誕快樂，諸位朋友們。
背包問題：就是現在有一個容量為 PSIZE 的背包，同時又有 N 件 item，現在要求將這些 item 放入這個背包裡面去，要求盡量放一定要求的 item（比如按照大小的順序），又要求放最多的 item 或者放的 item 權值之和要最大
問題講完，演算法如下，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
printf("nGreedyn");
if (classic ()==1){/* 經典算法 */
printf("Result");
for(i=0;i