李大仁博客

/*背包问题之经典解法和贪心算法
*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");
}