#include
#include
#include
#include
#include

using?namespace?std;
//定義問題的最大規模
#define?max?100
//為題規模，即共有多少個包
int?packageNum;
//每個包的重量
int?packageWeight[max]?=?{53111579136814};?
//每個包的價值
int?packageValue[max]?={100520100604090405080};
//約束，背包的最大容量
int?limitWeight;
//群體的規模
int?colonySize;
//colonyState[i][k]?表示一個染色體
//colonyState[1...conlonySize][0|1]?表示一個群體
int?colonyState[max][2][max];
//?currAge?表示當前代的編號
//?（currAge+1）%2?表示下一代的編號
int?currAge?=?0;
//?個體評價信息表

typedef?struct?tagIndivdualMsg
{
	int?index;
	int?value;
}IndivdualMsg;
IndivdualMsg?indivdualMsg[max];
/////////////////////////////////////////////////////////////
//函數聲明
void?printColonyState（int?nextAge）;
/////////////////////////////////////////////////////////////
//初始化群體
void?colonyInit（）
{
	int?i?j;
	int?w;

	for（i=0;?i	{
		//保證找到一個符合約束的染色體
		w?=?limitWeight?+1;
		while（w?>?limitWeight）
		{
			w?=?0;
			for（j=0;?j			{
				colonyState[i][currAge][j]?=?rand（）%2;
				w?+=?packageWeight[j]?*?colonyState[i][currAge][j];
			}
			
		}
	}
}

//對個體進行評價
int?cmp（const?void?*a?const?void?*b）
{
	IndivdualMsg?*x?=?（IndivdualMsg?*）a;
	IndivdualMsg?*y?=?（IndivdualMsg?*）b;
	return?y->value?-?x->value;
}
//適應度函數
void?indivdualEstimate（）
{
	int?i?j;
	for（i=0;?i	{
		indivdualMsg[i].index?=?i;
		indivdualMsg[i].value?=?0;
		for（j=0;?j			indivdualMsg[i].value?+=?packageValue[j]*colonyState[i][currAge][j];
	}
	qsort（indivdualMsg?colonySize?sizeof（IndivdualMsg）?cmp）;
}
//終止循環的條件
bool?stopFlag（）
{
	//進行n代進行后停止
	static?int?n?=?50;
	if（n--?<=?0）
		return?false;
	else
		return?true;
}
//賭輪選擇
int?gambleChoose（）
{
	int?wheel[max]?=?{0};
	int?i?=?colonySize-1;
	int?choose;
	wheel[i]?=?indivdualMsg[i].value;
	for（i--;?i>=0;?i--）
		wheel[i]?=?（indivdualMsg[i].value?+?wheel[i+1]）?+?colonySize*（colonySize-i）;
	int?seed?=?abs（wheel[0]-（rand（）%（2*wheel[0]+1）））;
	choose?=?colonySize-1;
	while（seed?>?wheel[choose]）
		choose--;
	return?choose;
}
//交叉
void?across（int?male?int?female?int?index）
{
	int?nextAge?=?（currAge+1）?%2;
	int?i?j?t;
	int?acrossBit?=?rand（）?%?（packageNum-1）?+?1;
	for（j=0;?j	{
		colonyState[index][nextAge][j]?=?colonyState[indivdualMsg[male].index][currAge][j];
		colonyState[index+1][nextAge][j]?=?colonyState[indivdualMsg[female].index][currAge][j];
	}

	for（i=0;?i	{
		t?=?colonyState[index][nextAge][i];
		colonyState[index][nextAge][i]?=?colonyState[index+1][nextAge][i];
		colonyState[index+1][nextAge][j]?=?t;
	}
}
//變異
void?aberrance（int?index）
{
	int?seed?nextAge;
	nextAge?=?（currAge+1）?%2;
	//只有1/3的概率發生異變
	seed?=?rand（）?%（packageNum*3）;
	if（seed?		colonyState[index][nextAge][seed]?=?（colonyState[index][nextAge][seed]?+?1）?%2;
}
//處理死亡個體
void?dealDeath（）
{
	int

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-06-02?20:46??遺傳算法解決背包問題\
?????文件??????615424??2013-05-22?16:58??遺傳算法解決背包問題\bag.exe
?????目錄???????????0??2013-06-02?20:45??遺傳算法解決背包問題\bag_code\
?????目錄???????????0??2013-06-02?20:45??遺傳算法解決背包問題\bag_code\Debug\
?????文件????????6786??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\BuildLog.htm
?????文件??????615424??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\bag.exe
?????文件?????????406??2013-05-22?16:58??遺傳算法解決背包問題\bag_code\Debug\bag.exe.embed.manifest
?????文件?????????472??2013-05-22?16:58??遺傳算法解決背包問題\bag_code\Debug\bag.exe.embed.manifest.res
?????文件?????????381??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\bag.exe.intermediate.manifest
?????文件?????1470088??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\bag.ilk
?????文件??????273583??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\bag.obj
?????文件?????3107840??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\bag.pdb
?????文件??????????67??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\mt.dep
?????文件???????74752??2010-04-05?19:15??遺傳算法解決背包問題\bag_code\Debug\vc60.idb
?????文件??????110592??2010-04-05?19:15??遺傳算法解決背包問題\bag_code\Debug\vc60.pdb
?????文件??????248832??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\vc90.idb
?????文件??????184320??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\Debug\vc90.pdb
?????文件???????18944??2013-05-22?13:34??遺傳算法解決背包問題\bag_code\Project1.exe
?????文件??????262144??2013-05-22?13:34??遺傳算法解決背包問題\bag_code\Project1.tds
?????文件????????6930??2013-05-22?21:47??遺傳算法解決背包問題\bag_code\bag.cpp
?????文件????????4248??2010-04-05?16:46??遺傳算法解決背包問題\bag_code\bag.dsp
?????文件?????????531??2010-04-05?13:21??遺傳算法解決背包問題\bag_code\bag.dsw
?????文件?????1231872??2013-05-26?21:12??遺傳算法解決背包問題\bag_code\bag.ncb
?????文件??????118175??2013-05-22?13:34??遺傳算法解決背包問題\bag_code\bag.obj
?????文件???????53760??2010-04-06?00:19??遺傳算法解決背包問題\bag_code\bag.opt
?????文件????????1248??2010-04-05?19:15??遺傳算法解決背包問題\bag_code\bag.plg
?????文件?????????876??2013-05-26?21:12??遺傳算法解決背包問題\bag_code\bag.sln
?????文件???????14848??2013-05-26?21:12??遺傳算法解決背包問題\bag_code\bag.suo
?????文件????????5129??2013-05-22?15:11??遺傳算法解決背包問題\bag_code\bag.vcproj
?????文件????????1413??2013-05-26?21:12??遺傳算法解決背包問題\bag_code\bag.vcproj.saniu-PC.saniu.user
?????文件???????????0??2003-07-23?17:52??遺傳算法解決背包問題\bag_code\bagItem.cpp
............此處省略1個文件信息