Home > 算法研究 > [算法]数据结构算法背包问题解法之递归解法,C语言实现

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

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

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


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

代码如下:
调试环境:GCC ,TC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
*背包问题之递归解法
*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 :w,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;
}
Categories: 算法研究 Tags: , ,
  1. December 31st, 2008 at 22:52 | #1

    祝新年快乐,牛B哄哄

  2. January 1st, 2009 at 13:37 | #2

    我C语言都没及格过%>_<%
    新年快乐

  3. January 1st, 2009 at 20:26 | #3

    元旦快乐!

  4. January 3rd, 2009 at 11:58 | #4

    新年快乐噢~!~

  5. January 3rd, 2009 at 23:30 | #5

    回看你的博客,加油

  6. January 4th, 2009 at 11:31 | #6

    朋友,应你的要求加你好友连接了,你也加我一下吧

  7. January 4th, 2009 at 13:44 | #7

    回访来啦!这里非常技术性啊。很深奥:) 我就是表面功夫的啦,以后要多跟你学习啦!

  8. January 4th, 2009 at 19:57 | #8

    好强的技术博客!

  1. No trackbacks yet.