今天講背包問題的最後一種解法，遞歸解法，這種解法也是目前算法教材上講的基本解法之一，如果你有一本關於這類算法的書籍，一般都可以找到你想要的算法，背包問題具體是什麼，大家可以參考我的以前的文章，可以直接到下面的相關鏈接裡面找到，我在最近發布關於背包問題的基本解法，動態規劃解法，回溯解法，大家可以直接參照我的頁面鏈接，如果具體還有問題不懂的話，也非常歡迎大家留言
好的，講一講遞歸算法，我提供的算法是使用了有效重量，最大可用價值作為遞歸參數逐個測試物件的重量和價值，直到找到最佳的侯返回，請注意，這裡我設置的條件是只要滿足背包可以放就可以，並不是貪心算法，請注意區別。
其他的問題相信大家看完代碼註釋就可以理解，如果大家還有不明白的地方，歡迎留言，我會儘量解答，最近博主要忙於考試，可能最近比較忙，所以還請見諒
代碼如下： 調試環境：GCC ，TC
/*
* 背包問題之遞歸解法
*code CG
*2008 12 30
*/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
#define N 5 /* 控制輸入的元素的個數 */
#define MAX 100 /* 背包最大可放重量 */
int result;
int select[N],selectW[N];
struct{
int weight;
int price;
} items [N]; /* 定義物件結構體 */
/*
*knapsacks () 背包遞歸算法
* 參數：int i 要放入的物件游標位置
int w 已用背包重量
int p 可使用的最大價格
*/
void knapsacks (int i, int w, int p){/* 背包遞歸算法 */
int k;
if ((w + items [i].weight) < = MAX){ /* 物品 I 重量放入背包是否滿足 */
selectW [i] = 1; /* 重量滿足，暫時放入背包 */
if (i < N - 1){/*i < N-1?*/
knapsacks(i + 1, w + items[i].weight, p);
}
else{
for (k = 0; k < N ; k++){
select[k] = selectW[k];/*selectW -> select*/
}/*for*/
result = p;
}/*else*/
}/*if*/
if (p - items [i].price > result){/* 如果物品 i 不放入背包的情況，還原 */
selectW[i] = 0;
if (i < N - 1){
knapsacks(i + 1, w ,p - items[i].price);
}
else{
for(k = 0; k < N; k++){/*selectW -> select*/
select[k] = selectW[k];
}
result = p - items[i].price;
}/*else*/
}/*if*/
}/*knapsacks*/
int main(){
int i;
int w = 0,v = 0;
int sumPrice = 0; /* 輸入計數器 */
int maxWeight = MAX;
printf("input W and V ,vn");
for (i = 0; i < N ; i++){
scanf("%d,%d",&w,&v);
items[i].weight = w;
items[i].price = v;
printf("W = %d,P = %dn",items[i].weight, items[i].price);
selectW [i] = 0; /* 清空記錄數組 */
select[i] = 0;
sumPrice += v; /* 記錄總價格數據 */
}/*for*/
printf("Max Weight:%dn", maxWeight);
result = 0;
printf("sumPrice:%dn", sumPrice);
knapsacks (0, 0, sumPrice);/* 開始背包操作 */
printf("| ID | WT | PR |n");
for (i = 0; i < N; i++){
if (select[i]){
printf("|%-4d|%-4d|%-4d|n",i+1,items[i].weight, items[i].price);
}
}/*for*/
printf("Result:%dn", result);
system("PAUSE");
return 0;
}