遗传算法解决01背包问题

本程序使用遗传算法来解决背包问题，0-1背包问题，使用C语言编写，带测试数据

#include
#include
#include 
#include 
#include 

#define ROUND 1500
#define INIT 100                //初始染色体数目
#define TotalGoods 50//30          //货物总数
#define Load       300//550         //背包总容量   
int Weights[TotalGoods];                  //存储每件货物重量数组    
int Values[TotalGoods];                   //存储每件货物价值数组
int TotalWeights[INIT];             //存储每个组合的总重量
int TotalValues[INIT];              //存储每个组合的总价值
double Fitness[INIT];                        //适应度

char ParentChromosome[INIT][TotalGoods+1];//存储父代基因组合，即染色体
char ChildChromosome[INIT][TotalGoods+1]; //存储子代基因组合，即染色体
double Prob[INIT];                   //每个组合的选择概率，用于轮盘赌选择
int count = 0;

/*******************************************************/
//读取配置文件             
//Line1:    货物重量
//Line2:    货物价值
//Line3……:备选初始组合，因为初始组合是随机产生的，不能保证满足“重量和<背包容量”，须在本程序中进行判断
/******************************************************/

void ReadConfFIle（char *filename）
{
	int i j;
	int sum=0;
	char *fname = filename;
	FILE *fid = fopen（fname “r“）;
	for （i=0; i< TotalGoods; i++）
	{
		fscanf（fid “%d“&Weights[i]）;
	}
	for （i=0; i< TotalGoods; i++）
	{
		fscanf（fid “%d“ &Values[i]）;
	}
	//从文件中读取满足约束条件的组合作为初始组合
	for （i=0; i< INIT; i++）
	{
		
		fscanf（fid “%s“ &ParentChromosome[i]）;
		sum=0;
		for （j=0; j< TotalGoods; j++）
		{
			sum += （int）（ParentChromosome[i][j]-48） * Weights[j];
		}
		if（sum >= Load）
		{
			i--;
		}
		
	}
	fclose（fid）;

}
/*******************************************/
//计算所有个体的适应度
//得到适应度数组
//输入：
//	  char Chromosome[][]: 父辈基因的组合
//输出：
//    double *fitness    : 所有基因组合的适应度
/******************************************/

void CalculateFitness（char  Chromosome[][TotalGoods+1]， double *fitness ）
{
	int ij;
	
	for （i=0; i< INIT; i++）
	{
		TotalValues[i] = 0;
		TotalWeights[i]=0;
		for （j=0; j< TotalGoods; j++）
		{
			TotalWeights[i]+=Weights[j]*（int）（Chromosome[i][j]-48）;
			TotalValues[i] +=Values[j] *（int）（Chromosome[i][j]-48）;
		}
		
		fitness[i]=（double）TotalValues[i];

	}

}
/********************************************************/
//通过轮盘赌来选择确定选择交叉的父染色体
//parent中存储了两个选择的父染色体的下标
//输入：
//     double *fitness: 适应度，即每一个组合的价值
//     double *prob   : 每个组合的选择概率
//输出：
//     int *parent    : 选择出来的两个父染色体的标号
/*******************************************************/

void RoundRobinSelection（double *fitness double *prob int *parent）
{
	double FintnessSum = 0;
	int i j;
	double r1 r2 r;
	double ProbSum=0;
	int parent1 parent2;
	
	for （i=0; i< INIT; i++）
	{
		FintnessSum += fitness[i];
	}
	for （i=0; i< INIT; i++）
	{
		prob[i] = （float）fitness[i] / FintnessSum; 
	}
	

	r1 = rand（） /（double） （RAND_MAX）;
	r2 = rand（）/（double） （RAND_MAX）;
	if（r1>r2）
	{
		r= r1;
		r1 = r2;
		r2 = r;
	}

	for （i=0; i< INIT-1; i++）
	{
		if （ProbSum < r1 && ProbSum + prob[i] >= r1）
		{
			parent[0] = i;
			break;
		}
		ProbSum += prob[i];
	}
	f

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     531968  2015-03-06 16:13  GA_Knapsack\0-1背包问题测试数据（提供参考）.xls

     文件      31232  2015-03-06 20:15  GA_Knapsack\Debug\GA_Knapsack.exe

     文件     404552  2015-03-06 20:15  GA_Knapsack\Debug\GA_Knapsack.ilk

     文件     429056  2015-03-06 20:15  GA_Knapsack\Debug\GA_Knapsack.pdb

     文件      11734  2015-03-06 20:15  GA_Knapsack\GA_Knapsack\Debug\BuildLog.htm

     文件      19488  2015-03-06 20:15  GA_Knapsack\GA_Knapsack\Debug\GA.obj

     文件        663  2015-03-06 11:40  GA_Knapsack\GA_Knapsack\Debug\GA_Knapsack.exe.embed.manifest

     文件        728  2015-03-06 11:40  GA_Knapsack\GA_Knapsack\Debug\GA_Knapsack.exe.embed.manifest.res

     文件        621  2015-03-06 20:15  GA_Knapsack\GA_Knapsack\Debug\GA_Knapsack.exe.intermediate.manifest

     文件         65  2015-03-06 20:15  GA_Knapsack\GA_Knapsack\Debug\mt.dep

     文件      60416  2015-03-06 20:15  GA_Knapsack\GA_Knapsack\Debug\vc90.idb

     文件      69632  2015-03-06 20:15  GA_Knapsack\GA_Knapsack\Debug\vc90.pdb

     文件       6754  2015-03-06 20:39  GA_Knapsack\GA_Knapsack\GA.cpp

     文件       3980  2015-03-06 11:38  GA_Knapsack\GA_Knapsack\GA_Knapsack.vcproj

     文件       1421  2015-03-06 20:39  GA_Knapsack\GA_Knapsack\GA_Knapsack.vcproj.STAP1ZWWA147.Administrator.user

     文件       3554  2015-03-06 13:05  GA_Knapsack\GA_Knapsack\input.txt

     文件        983  2015-03-06 20:47  GA_Knapsack\GA_Knapsack\ReadMe.txt

     文件     133246  2015-03-06 20:17  GA_Knapsack\GA_Knapsack\result.txt

     文件      15993  2015-03-06 19:24  GA_Knapsack\GA_Knapsack\test.txt

     文件          0  2015-03-06 19:59  GA_Knapsack\GA_Knapsack\test2.txt

     文件     584704  2015-03-06 20:39  GA_Knapsack\GA_Knapsack.ncb

     文件        899  2015-03-06 11:07  GA_Knapsack\GA_Knapsack.sln

    ..A..H.     17408  2015-03-06 20:39  GA_Knapsack\GA_Knapsack.suo

     目录          0  2015-03-06 20:15  GA_Knapsack\GA_Knapsack\Debug

     目录          0  2015-03-06 16:22  GA_Knapsack\Debug

     目录          0  2015-03-06 20:39  GA_Knapsack\GA_Knapsack

     目录          0  2015-03-06 20:47  GA_Knapsack

----------- ---------  ---------- -----  ----

              2329097                    27



............此处省略0个文件信息