李大仁博客

[算法]数据结构算法背包问题解法之递归解法，C语言实现

李大仁

今天讲背包问题的最后一种解法，递归解法，这种解法也是目前算法教材上讲的基本解法之一，如果你有一本关于这类算法的书籍，一般都可以找到你想要的算法，背包问题具体是什么，大家可以参考我的以前的文章，可以直接到下面的相关链接里面找到，我在最近发布关于背包问题的基本解法，动态规划解法，回溯解法，大家可以直接参照我的页面链接，如果具体还有问题不懂的话，也非常欢迎大家留言

好的，讲一讲递归算法，我提供的算法是使用了有效重量，最大可用价值作为递归参数逐个测试物件的重量和价值，直到找到最佳的侯返回，请注意，这里我设置的条件是只要满足背包可以放就可以，并不是贪心算法，请注意区别。


其他的问题相信大家看完代码注释就可以理解，如果大家还有不明白的地方，欢迎留言，我会尽量解答，最近博主要忙于考试，可能最近比价忙，所以还请见谅

代码如下：
调试环境：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)  select*/
          }/*for*/
      result = p;
      }/*else*/
    }/*if*/
    if (p - items[i].price > result){/*如果物品i不放入背包的情况，还原 */
      selectW[i] = 0;
      if (i  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 :w,vn");
for (i = 0; i
Exit mobile version