今天讲背包问题的最后一种解法，递归解法，这种解法也是目前算法教材上讲的基本解法之一，如果你有一本关于这类算法的书籍，一般都可以找到你想要的算法，背包问题具体是什么，大家可以参考我的以前的文章，可以直接到下面的相关链接里面找到，我在最近发布关于背包问题的基本解法，动态规划解法，回溯解法，大家可以直接参照我的页面链接，如果具体还有问题不懂的话，也非常欢迎大家留言
好的，讲一讲递归算法，我提供的算法是使用了有效重量，最大可用价值作为递归参数逐个测试物件的重量和价值，直到找到最佳的侯返回，请注意，这里我设置的条件是只要满足背包可以放就可以，并不是贪心算法，请注意区别。
其他的问题相信大家看完代码注释就可以理解，如果大家还有不明白的地方，欢迎留言，我会尽量解答，最近博主要忙于考试，可能最近比价忙，所以还请见谅
代码如下： 调试环境：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;
}