求高手帮我用C语言写一个运用贪心和遗传算法求解背包问题的程序。。。。谢谢！！！！！！十分紧急！！！

Question

如题所述

Answer 1

1、程序开发环境
   å¼€å‘环境：Visual C++6.0 (把Fortran程序改为VC)
   æ“ä½œç³»ç»Ÿï¼šWindows 2003 Professional
2、程序性能对比
    è¿è¡Œæ—¶é—´ä¸ŽåŠ é€Ÿæ¯”（如表1所示）
进程数p（个） 1 2 4 
运行时间t（秒） 129s 78s 38s 
加速比s  1.65 3.38 
 è¡¨1、运行时间与加速比
3、程序运行结果：
  å®žä¾‹æ•°æ®ï¼š
 å‡è®¾ç‰©ä½“的重量Weight、物体的收益Profit和背包的容量Contain åˆ†åˆ«ä¸ºï¼š
Weight={ 80，82，85，70，72，    70，66，50，55，25 ï¼Œ
   50，55，40，48，50，     32，22，60，30，32 ï¼Œ 
 40，38，35，32，25，     28，30，22，50，30 ï¼Œ
 45，30，60，50，20 ï¼Œ    65，20，25，30，10 ï¼Œ
 20，25，15，10，10 ï¼Œ    10，4， 4， 2， 1   }
Profit={  220，208，198，192，180，    180，165，162，160，158，
 155，130，125，122，120 ï¼Œ   118，115，110，105，101，
 100，100，98， 96， 95，     90， 88， 82， 80， 77 ï¼Œ
 75， 73， 72， 70， 69，     66， 65， 63， 60， 58，
 56， 50， 30， 20， 15，      10， 8，  5，  3，  1}
Contain=1000，
 å¦‚何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大?
 ä¼ ç»Ÿçš„算法（动态规划、递归回溯法和贪心算法所得结果：  
      æ€»ä»·å€¼ä¸º3077 , æ€»é‡é‡ä¸º999。
 2001年张铃，张钹教授在计算机学报上发表的《佳点集遗传算法》所得结果
 æ€»ä»·å€¼ä¸º3103, æ€»é‡é‡ä¸º1000。
 æˆ‘们算法所得结果：                   æ€»ä»·å€¼ä¸º3103, æ€»é‡é‡ä¸º1000。
 æˆ‘们所求得最优解的个体分配情况为：
11010   10111   10110   11011   01111   11101   00001   01001   10000   
01000
算法 æœ€å¤§è¿­ä»£æ¬¡æ•° æ€»ä»·å€¼ä¸º æ€»é‡é‡ä¸º 
传统的算法 400 3077 999 
佳点集算法 70 3103 1000 
遗传算法    75 3103 1000 

// knapsack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <AfxWin.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>

// é‡è¦å¸¸é‡å‚æ•°
#define popsize 200   //种群的规模
#define pc 0.618        //杂交概率
#define pm 0.03        //变异概率
#define lchrom 50      //染色体长度
#define maxgen 1000     //最大进化代数

struct population
{
 unsigned int chrom[lchrom];   //染色体
 double weight;                //背包重量
 double fitness;               //适应度
 unsigned int parent1,parent2,cross;  //双亲、交叉点
};

//新生代种群、父代种群
struct population oldpop[popsize],newpop[popsize]; 

//背包问题中物体重量、收益、背包容量
int weight[lchrom],profit[lchrom],contain; 

//种群的总适应度、最小、最大、平均适应度 
double sumfitness,minfitness,maxfitness,avgfitness;

//计算适应度时使用的 æƒ©ç½šå‡½æ•°ç³»æ•°
double alpha;

//一个种群中最大和最小适应度的个体
int    minpop,maxpop; 

/* è¯»å…¥èƒŒåŒ…信息,并且计算惩罚函数系数 */
void read_infor()
{
 FILE *fp;
 int j;
    
 //获取背包问题信息文件
 if ((fp=fopen("knapsack.txt","r"))==NULL)
 {   
  //读取文件失败
  AfxMessageBox("The file is not found",MB_OK,NULL);
     return;
 }
 //读入物体收益信息
    for (j=0;j<lchrom;j++)
    {
     fscanf(fp,"%d",&profit[j]);
    }
 //读入物体重量信息
    for (j=0;j<lchrom;j++)
    {
     fscanf(fp,"%d",&weight[j]);
    } 
 //读入背包容量
    fscanf(fp,"%d",&contain);
    fclose(fp);
 
}

//根据计算的个体重量,判断此个体是否该留在群体中
double cal_weight(unsigned int *chr)
{
  int j;
  double pop_weight;//背包重量

  pop_weight=0;
  for (j=0;j<lchrom;j++)
  {
 pop_weight=pop_weight+(*chr)*weight[j];
 chr++;
  }
  return pop_weight;
}

/* ç§ç¾¤ä¸­ä¸ªä½“适应度计算*/
double cal_fit(unsigned int *chr)
{
  int j;
  double pop_profit;//适应度

  pop_profit=0;
//  pop_weight=0;

  for (j=0;j<lchrom;j++)
  {
 pop_profit=pop_profit+(*chr)*profit[j];
// pop_weight=pop_weight+(*chr)*weight[j];
 chr++;
  }
  
  return pop_profit;
}

/* ç¾¤ä½“适应度的最大最小值以及其他信息 */
void statistics(struct population *pop)
{
 int i;
 double tmp_fit;

 sumfitness=pop[0].fitness;
 minfitness=pop[0].fitness;
    minpop=0;
 maxfitness=pop[0].fitness;
 maxpop=0;
 
 for (i=1;i<popsize;i++)
 {
  //计算种群的总适应度
  sumfitness=sumfitness+pop[i].fitness;
        tmp_fit=pop[i].fitness;
  //选择种群中最大适应度的个体
  if ((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))
  {
   maxfitness=pop[i].fitness;
   maxpop=i;
  }

        //选择种群中最小适应度的个体
  if (tmp_fit<minfitness)
  {
   minfitness=pop[i].fitness;
   minpop=i;
  }
  
  //计算平均适应度
  avgfitness=sumfitness/(float)popsize;
 }
//  printf("\nthe max pop = %d;",maxpop);
//  printf("\nthe min pop = %d;",minpop);
//   printf("\nthe sumfitness = %f\n",sumfitness);
}

//报告种群信息
void report(struct population *pop,int gen)
{
      int j;
   int pop_weight=0;

   printf("the generation is %d.\n",gen); //输出种群的代数    
   //输出种群中最大适应度个体的染色体信息
   printf("The population's chrom is:  \n");
   for (j=0;j<lchrom;j++)
   { 
  if (j%5==0) 
  {  printf(" ");}
  printf("%1d",pop[maxpop].chrom[j]);
   }
   //输出群体中最大适应度
      printf("\nThe population's max fitness is %d.",(int)pop[maxpop].fitness);
      printf("\nThe knapsack weight is %d.\n\n",(int)pop[maxpop].weight);

}

/* ç”Ÿæˆåˆå§‹ç§ç¾¤ */
void initpop()
{
  int i,j,ispop;
  double tmpWeight;
  //变量用于判断是否为满足条件的个体
  ispop=false;

  //生成popsize个种群个体
  for(i=0;i<popsize;i++)
  {
     while (!ispop)
  {
    for(j=0;j<lchrom;j++)
    {
    oldpop[i].chrom[j]=rand()%2;   //随机生成个体的染色体
       oldpop[i].parent1=0;  //双亲
       oldpop[i].parent2=0;
       oldpop[i].cross=0;    //交叉点
    }

    //选择重量小于背包容量的个体,即满足条件
       tmpWeight=cal_weight(oldpop[i].chrom);
    if (tmpWeight<=contain)
    {
    oldpop[i].fitness=cal_fit(oldpop[i].chrom);
    oldpop[i].weight=tmpWeight;
    oldpop[i].parent1=0;
    oldpop[i].parent2=0;
    oldpop[i].cross=0;
    ispop=true;
    }
  }
  //此个体可以加入到种群中
  ispop=false;
  }
}

/*  é—传操作   */

//概率选择试验
int execise(double probability)
{
 double pp;
    //如果生成随机数大于相应的概率则返回真，否则试验不成功
 pp=(double)(rand()%20001/20000.0);
 if (pp<=probability) return 1;
 return 0;
}

// é€‰æ‹©è¿›è¡Œäº¤å‰æ“ä½œçš„个体 
int selection(int pop)
{
  double wheel_pos,rand_Number,partsum;
  int parent;

  //赌轮法选择
  rand_Number=(rand()%2001)/2000.0;
  wheel_pos=rand_Number*sumfitness;  //赌轮大小

  partsum=0;
  parent=0;
  do{
   partsum=partsum+oldpop[parent].fitness;
   parent=parent+1;
 } while (partsum<wheel_pos && parent<popsize);
  return parent-1;

}

/*  äº¤å‰æ“ä½œ  */
int crossover(unsigned int *parent1,unsigned int *parent2,int i)
{
 int j,cross_pos;
 if (execise(pc))
 {
  //生成交叉位置0,1,...(lchrom-2)
  cross_pos=rand()%(lchrom-1);
 }
 else cross_pos=lchrom-1;
    
 for (j=0;j<=cross_pos;j++)
 {   //保留复制；
  //包括在概率选择不成功时，父体完全保留
  newpop[i].chrom[j]=parent1[j];
 }
 for(j=cross_pos+1;j<=(lchrom-1);j++)
 {
  //从交叉点开始交叉
  newpop[i].chrom[j]=parent2[j];
 }
    
 //记录交叉位置
 newpop[i].cross=cross_pos;
 return 1;
}

/*  å˜å¼‚操作 */
int mutation(unsigned int alleles)
{
   if (execise(pm))
   {
    if (alleles)
     alleles=0;
    else alleles=1;
   }
   //返回变异值，或者返回原值
   return alleles;
}

/* ç¾¤ä½“æ›´æ–° */
void generation()
{
  unsigned int i,j,mate1,mate2;
  double tmpWeight;
  int ispop;//记录是否是符合条件的个体
  i=0;
  while (i<popsize)
  {
 ispop=false;
    while (!ispop)
  {
     //选择
     mate1=selection(i);
     mate2=selection(i+1);

        //交叉
        crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);

     //变异
        for (j=0;j<lchrom;j++)
  {
        newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);
  }

     //选择重量小于背包容量的个体,即满足条件
        tmpWeight=cal_weight(newpop[i].chrom);
     if (tmpWeight<=contain)
  {
    newpop[i].fitness=cal_fit(newpop[i].chrom);
    newpop[i].weight=tmpWeight;
    newpop[i].parent1=mate1;
    newpop[i].parent2=mate2;
    ispop=true;
  }
  }
  //此个体可以加入到种群中
    i=i+1;
  }
}

void main(int argc, char* argv[])
{
 int gen,oldmaxpop,k;
 double oldmax;
      
    read_infor();//读入背包信息
 gen=0;
 srand( (unsigned)time( NULL ) );//置随机种子
 initpop();
 memcpy(&newpop,&oldpop,popsize*sizeof(struct population));
 statistics(newpop);//统计新生种群的信息
 report(newpop,gen);
 while(gen<maxgen)
 {
   gen=gen+1;
   if (gen%100==0)
   {
    srand( (unsigned)time( NULL ) );//置随机种子
   }
   oldmax=maxfitness;
   oldmaxpop=maxpop;
   generation();
   statistics(newpop); //统计新生代种群信息
   //如果新生代种群中个体的最大适应度小于老一代种群
   //个体的最大适应度，则保存老一代种群个体的最大适应度
   //否则报告新生代的最大适应度
   if (maxfitness<oldmax)
   {
    for(k=0;k<lchrom;k++)
     newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k];
    newpop[minpop].fitness=oldpop[oldmaxpop].fitness;
    newpop[minpop].parent1=oldpop[oldmaxpop].parent1;
          newpop[minpop].parent2=oldpop[oldmaxpop].parent2;
    newpop[minpop].cross=oldpop[oldmaxpop].cross;
    statistics(newpop);
   }
   else if (maxfitness>oldmax)
     {
        report(newpop,gen);
   }

   //保存新生代种群的信息到老一代种群信息空间
   memcpy(&oldpop,&newpop,popsize*sizeof(struct population));
    }

 printf("It is over.");
 getch();
}追问

这个没有贪心算法的，能不能求一个两个相结合的啊？？？

追答

背包还能用贪心解吗？
除了这个我只知道搜索和动态规划

Answer 2

背包问题只能是动态规划求解的吧。。。。遗传这种智能算法。。。。不评价