Home > 算法研究 > [算法]背包问题的经典算法和贪心算法解答,C语言实现

[算法]背包问题的经典算法和贪心算法解答,C语言实现

圣诞前夜讲点比较具有圣诞感觉的算法,背包问题算法,这里我写了经典算法和贪心算法两种解决方法,因为时间不多,所以给出的数组是已经排序的,因为贪心算法可能要用得到,经典算法因为是一个一个比较,因此排序也就没有那么重要了,可能两种算法的最终运行效果一样的,朋友们调试的时候记得修改我给出的测试数组,今天实在太忙了,贪心使用的排序算法没有写,留着以后给大家讲排序算法的时候使用吧,圣诞快乐,诸位朋友们。

背包问题:就是现在有一个容量为PSIZE的背包,同时又有N件item,现在要求将这些item放入这个背包里面去,要求尽量放一定要求的item(比如按照大小的顺序),又要求放最多的item或者放的item权值之和要最大


问题讲完,算法如下,C语言实现,另外回溯、动态规划的算法,有时间也会写上,今天
实在太忙了,诸位朋友继续期待吧:

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
84
85
86
87
88
89
90
/*背包问题之经典解法和贪心算法
*code cg
*2008 12 24
*调试环境TC ,devC++
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 5 /*定义需要放的物件数量*/
#define PSIZE 150/*定义背包大小*/
 
long item[N]={15,40,50,60,90};/*初始化物件数组,贪心算法要求大小已排序*/
int freespace[N]={0};
 
int classic() {/*经典算法*/
long size = PSIZE;
long used = 0;
int i;
 for(i = N - 1 ; i >= 0 ; i--){
  if((size - used) >= item[i]){/*大小可以放入吗?*/
   used += item[i]; /*放入背包 已使用数加新物件的大小*/
   freespace[i] = 1;
  }
   else { /*大小太大*/
  freespace[i] = 0;
  }
 }/*for*/
 return 1;
}
 
int greedy(){/*贪婪算法*/
int i;
long size = PSIZE;
long used = 0;
for(i = N - 1 ; i >= 0 ; i--){/*先放大的物体,再考虑小的物体*/
 if( (used + item[i]) < = size){/*如果当前物体可以放入*/
  freespace[i] = 1;/*1表示放入*/
  used += item[i];/*背包剩余容量减少*/
 }
 else{
  freespace[i]=0;
 }
}/*for*/
if(size == used)/*返回*/
 return 1;
else
 return 0;
}
 
void main()
{
int i;/*计数器*/
for(i = 0 ; i < N ; i++){
 if(i % 5 == 0 )
  printf("n");
 printf("%10ld" , item[i]);/*首先输入原始数据*/
 }/*for*/
printf("nClassicn");
if(classic()==1){/*经典算法*/
 printf("Result:n");
 for(i=0;i<n;i++){/*输出*/
  if(freespace[i] == 1){
   if(i % 5 == 0)
    printf("n");
  printf("%10ld" , item[i]);
  }/*if*/
 }/*for*/
}/*if*/
else {
 printf("nNo Resultn");
}
for(i = 0 ; i < N ; i++)
 freespace[i]=0 ; /*清空freespace数组*/
 
printf("nGreedyn");
if(classic()==1){/*经典算法*/
 printf("Result:n");
 for(i=0;i<n;i++){/*输出*/
  if(freespace[i] == 1){
   if(i % 5 == 0)
    printf("n");
  printf("%10ld" , item[i]);
  }/*if*/
 }/*for*/
}/*if*/
else{
 printf("nNo Resultn");
 }
system("PAUSE");
}
Categories: 算法研究 Tags: ,
  1. December 25th, 2008 at 09:23 | #1

    呵呵 是不是软件工程专业的啊,博客的主人?

    我读书的时候也是这个专业!

  2. December 25th, 2008 at 12:42 | #2

    呵呵,算是同行吧,我学的主要方向是软件设计,比较枯燥吧

  3. December 25th, 2008 at 14:07 | #3

    我关注软件,但不搞软件

  4. December 25th, 2008 at 18:03 | #4

    唉~~本人没有兴趣~~~没事不来了~~88~再见

  5. December 25th, 2008 at 22:24 | #5

    CG啥时候要教我C…

  6. January 31st, 2009 at 11:56 | #6

    呵呵……不错,我学的是网络工程,不过快毕业了,签到的工作也是搞软件开发。
    博主,做个友情链接吧……

  1. No trackbacks yet.