基于遗传算法求解01背包问题

#include 
#include 
#include “math.h“
#include “time.h“
#include “stdlib.h“

using namespace std;


#define PopSize 8
#define Max 10000

typedef struct
{
	char objectName[10];//物品名称
	int Volume;//物品体积
	int Benefit;//物品效益
}object;
//标志物体的结构体

typedef struct
{
	int *chrom;//染色体
	int fitness;//适应度
}Individual;
//标志染色体的结构体

object *object/*存储物品信息的数组*/;
Individual *oldpop*newpopbest;

int MaxVolume（int object_Num）
{
	//求背包中体积最大的物品的体积
	int maxi;
	max=object[0].Volume;
	for（i=1;iject_Num;i++）
	{
		if（object[i].Volume>max）
			max=object[i].Volume;
	}
	return max;
}

//OK
int MinVolume（int object_Num）
{
	//求背包中体积最小的物品的体积
	int mini;
	min=object[0].Volume;
	for（i=1;iject_Num;i++）
	{
		if（object[i].Volume			min=object[i].Volume;
	}
	return min;
}

//OK
void Malloc（int ChromSize）
{
	//内存空间的分配
	int i;
	oldpop=new Individual[PopSize];
	newpop=new Individual[PopSize];
	for（i=0;i	{
		oldpop[i].chrom=new int[ChromSize];
		newpop[i].chrom=new int[ChromSize];
	}
	best.chrom=new int[ChromSize];
}

//OK
int Fitness（int chrom[]int ChromSize）
{
	//计算一条染色体的适应度
	int ifitness=0;
	for（i=0;i	{
		fitness+=object[i].Benefit*（chrom[i]）;
	}
	return fitness;
}
//;;;;;;;;;;适应度的计算;;;;;;;;;;;;;;;
int SumFitness（Individual Pop[]int ChromSize）
{
	//求一个种群的总适应度
	int isumfitness=0;
	for（i=0;i	{
		sumfitness+=Fitness（Pop[i].chromChromSize）;
	}
	return sumfitness;
}

int CurrentVolume（int chrom[]int ChromSize）
{
	//计算当前方案背包中已放物品体积和
	int ivolume=0;
	for（i=0;i	{
		volume+=object[i].Volume*（chrom[i]）;
	}
	return volume;
}
//;;;;;;;;;;背包当前体积的计算;;;;;;;;;;;;;;;
int SumVolume（Individual *Popint ChromSize）
{
	int isumvolume=0;
	for（i=0;i	{
		sumvolume+=CurrentVolume（Pop[i].chromChromSize）;
	}
	return sumvolume;
}
int Volume_All_object（int ChromSize）
{
	int SumVolume=0i;
	for（i=0;i		SumVolume+=object[i].Volume;
	return SumVolume;
}
void Initilize（int ChromSizeint PossibleNum）
{
	//;;;;;;;;;初始化一个种群;;;;;;;;;;
	srand（（unsigned）time（NULL））;
	int ijlocation;
	for（i=0;i		for（j=0;j		{
			oldpop[i].chrom[j]=0;
			newpop[i].chrom[j]=0;
		}

		for（i=0;i		{
			for（j=0;j			{
				location=rand（）%ChromSize;
				if（oldpop[i].chrom[location]==0）
				{
					oldpop[i].chrom[location]=1;
					j++;
				}
			}
		}
}

void Order_Best_First（int ChromSizeint Pop_SizeIndividual Pop[]）
{
	//;;;;;;;;;;;;;;选择优秀子代;;;;;;;;;;;;;;;;;
	//;;;;;;;;;;排在前面的优于排在后面的;;;;;;;;;
	Individual temp;
	int ij;
	for（i=0;i		for（j=0;j		{
			if（Pop[j].fitness			{
				temp=Pop[j];
				Pop[j]=Pop[j+1];
				Pop[j+1]=temp;
			}
		}
}

Individual Select（int ChromSizeIndividual Pop[]）
{
	int Num_SelectedijChrom_Selected_FromChrom_Select

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

     文件       8192  2011-04-03 10:39  遗传算法_背包问题DebugBuildLog.htm

     文件     287744  2011-04-04 19:25  遗传算法_背包问题DebugInherit.bsc

     文件     573549  2011-04-04 19:25  遗传算法_背包问题DebugInherit.exe

     文件        406  2011-03-28 10:39  遗传算法_背包问题DebugInherit.exe.embed.manifest

     文件        472  2011-03-28 10:39  遗传算法_背包问题DebugInherit.exe.embed.manifest.res

     文件        381  2011-04-03 10:39  遗传算法_背包问题DebugInherit.exe.intermediate.manifest

     文件     810888  2011-04-04 19:25  遗传算法_背包问题DebugInherit.ilk

     文件     267385  2011-04-04 19:24  遗传算法_背包问题DebugInherit.obj

     文件    2087608  2011-04-04 19:24  遗传算法_背包问题DebugInherit.pch

     文件    1139712  2011-04-04 19:25  遗传算法_背包问题DebugInherit.pdb

     文件          0  2011-04-04 19:25  遗传算法_背包问题DebugInherit.sbr

     文件         65  2011-04-03 10:39  遗传算法_背包问题Debugmt.dep

     文件     123904  2011-12-13 20:52  遗传算法_背包问题Debugvc60.idb

     文件     110592  2011-04-04 19:24  遗传算法_背包问题Debugvc60.pdb

     文件      84992  2011-04-03 10:39  遗传算法_背包问题Debugvc90.idb

     文件     184320  2011-04-03 10:39  遗传算法_背包问题Debugvc90.pdb

     文件       9261  2011-04-03 10:39  遗传算法_背包问题Inherit.cpp

     文件       3417  2011-04-01 21:23  遗传算法_背包问题Inherit.dsp

     文件        539  2011-04-01 21:23  遗传算法_背包问题Inherit.dsw

     文件       2385  2011-03-24 21:14  遗传算法_背包问题Inherit.h

     文件      50176  2011-12-13 20:52  遗传算法_背包问题Inherit.ncb

     文件      53760  2011-12-13 20:52  遗传算法_背包问题Inherit.opt

     文件        248  2011-12-13 20:52  遗传算法_背包问题Inherit.plg

     文件        884  2011-04-03 11:53  遗传算法_背包问题Inherit.sln

    ..A..H.     11776  2011-11-28 19:31  遗传算法_背包问题Inherit.suo

     文件       3978  2011-03-26 14:03  遗传算法_背包问题Inherit.vcproj

     文件       1412  2011-04-03 11:53  遗传算法_背包问题Inherit.vcproj.admin-PC.admin.user

     文件        146  2011-04-01 17:12  遗传算法_背包问题InheritData.dat

     目录          0  2011-11-28 10:42  遗传算法_背包问题Debug

     目录          0  2011-12-13 20:52  遗传算法_背包问题

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