今天講點簡單的演算法，最簡單的背包 0 演算法，使用了遞歸的方法，相信看完程式的朋友會發現這段程式碼很熟悉，不過 CG 提供這些程式碼的目的只是讓全部背包演算法的完整提供地給大家，程式碼很簡單，相信高手一看就懂，這裡的背包演算法只是考慮了物品的重量，沒有考慮物品的價值，是初學遞歸演算法的朋友必看的程式碼，高手的話全當複習一下吧。 因為 CG 最近要考試了，一口氣要考 6 門，所以部落格更新沒有這麼快了，請大家見諒不過我還是會保持每天提供至少一篇的速度寫部落格文章，希望大家能支持，謝謝 預告下明天的演算法部落格文章，《銀行家演算法》，今天複習了下作業系統，晚上重新安裝了系統，浪費了兩個小時，程式碼明天調試後奉上，希望大家繼續關注。
/* 簡單的背包問題遞歸解
*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*/