#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??遺傳算法_背包問題\Debug\BuildLog.htm

?????文件?????287744??2011-04-04?19:25??遺傳算法_背包問題\Debug\Inherit.bsc

?????文件?????573549??2011-04-04?19:25??遺傳算法_背包問題\Debug\Inherit.exe

?????文件????????406??2011-03-28?10:39??遺傳算法_背包問題\Debug\Inherit.exe.embed.manifest

?????文件????????472??2011-03-28?10:39??遺傳算法_背包問題\Debug\Inherit.exe.embed.manifest.res

?????文件????????381??2011-04-03?10:39??遺傳算法_背包問題\Debug\Inherit.exe.intermediate.manifest

?????文件?????810888??2011-04-04?19:25??遺傳算法_背包問題\Debug\Inherit.ilk

?????文件?????267385??2011-04-04?19:24??遺傳算法_背包問題\Debug\Inherit.obj

?????文件????2087608??2011-04-04?19:24??遺傳算法_背包問題\Debug\Inherit.pch

?????文件????1139712??2011-04-04?19:25??遺傳算法_背包問題\Debug\Inherit.pdb

?????文件??????????0??2011-04-04?19:25??遺傳算法_背包問題\Debug\Inherit.sbr

?????文件?????????65??2011-04-03?10:39??遺傳算法_背包問題\Debug\mt.dep

?????文件?????123904??2011-12-13?20:52??遺傳算法_背包問題\Debug\vc60.idb

?????文件?????110592??2011-04-04?19:24??遺傳算法_背包問題\Debug\vc60.pdb

?????文件??????84992??2011-04-03?10:39??遺傳算法_背包問題\Debug\vc90.idb

?????文件?????184320??2011-04-03?10:39??遺傳算法_背包問題\Debug\vc90.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個文件信息