人工智能-背包问题

背包问题1.实验目的给定一个载重量为m，n个物品，其重量为wi，价值为vi，1=i=n，要求:把物品装入背包，并使包内物品价值最大。2.问题分析在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。循环变量i，j意义：前i个物品能够装入载重量为j的背包中。(n+1)*(m+1)数组value意义：value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值,若w[i]j，第i个物品不装入背包,否则，若w[i]=j且第i个物品装入背包后的价值value[i-1][j]，则记录当前最大价值（替换为第i个物品装入背包后的价值）。计算最大价值的动态规划算法如下：//计算for(i=1;irow;i++){for(j=1;jcol;j++){//w[i]j,第i个物品不装入背包value[i][j]=value[i-1][j];//w[i]=j,且第i个物品装入背包后的价值value[i-1][j],则记录当前最大价值inttemp=value[i-1][j-w[i]]+v[i];if(w[i]=j&&tempvalue[i][j])value[i][j]=temp;}}即该段程序完成以下n个阶段：1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值。2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值。。。。n：以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值。3.算法步骤确定装入背包的具体物品，从value[n][m]向前逆推：若value[n][m]value[n-1][m]，则第n个物品被装入背包，且前n-1个物品被装入载重量为m-w[n]的背包中。否则，第n个物品没有装入背包，且前n-1个物品被装入载重量为m的背包中。以此类推，直到确定第一个物品是否被装入背包为止。逆推代码如下：//逆推求装入的物品j=m;for(i=row-1;i0;i--){if(value[i][j]value[i-1][j]){c[i]=1;j-=w[i];}}4.结果分析给定一个载重量为m，n个物品，其重量为wi，价值为vi，1=i=n，要求:把物品装入背包，并使包内物品价值最大。输入数据及输出数据均在文件中。输入数据格式：nmw1w2...wnv1v2...vn输出数据格式：maxValueicount//i表示物品编号，count表示该物品被选中次数文件中的内容如下：1.input.txt41023471359input_result.txt1221412.input2.txt5102265463546input1_result.txt151121513.input3.txt101051216247293254331111161592425332417input3_result.txt1121121416171911015.实验体会6.结束语7.参考文献[1]林鑫；基于0/1背包问题的讨论[J]；微机发展；2005年10期[2]姜宇;苏中滨;郑萍;求解O/1背包问题的算法综述[A];黑龙江省计算机学会2009年学术交流年会论文集[C];2010年[3]马良,王龙德;背包问题的蚂蚁优化算法[J];计算机应用;2001年08期[4]贾欣鑫;罗亮;郭丽峰;何尚录;;求解复杂背包问题的一种贪婪算法[J];重庆工学院学报(自然科学版);2008年09期[5]王晓东.算法设计与分析[M].北京：清华大学出版设，20038．程序源代码/*************************************************************************0/1背包问题求解(VisualC++2006)*给定一个载重量为m,及n个物品,其重量为wi,价值为vi,1=i=n*要求:把物品装入背包,并使包内物品价值最大************************************************************************/#includestdio.h#includestdlib.h#includestring.h#defineFILENAMELENGTH100classCBeibao{public:intm_nNumber;//物品数量intm_nMaxWeight;//最大载重量int*m_pWeight;//每个物品的重量int*m_pValue;//每个物品的价值int*m_pCount;//每个物品被选中的次数intm_nMaxValue;//最大价值public:CBeibao(constchar*filename);~CBeibao();intGetMaxValue();intGetMaxValue(intn,intm,int*w,int*v,int*c);voidDisplay(intnMaxValue);voidDisplay(intnMaxValue,constchar*filename);};//读入数据CBeibao::CBeibao(constchar*filename){FILE*fp=fopen(filename,r);if(fp==NULL){printf(cannotopenfile!);return;//exit(0);}//读入物品数量和最大载重量fscanf(fp,%d%d,&m_nNumber,&m_nMaxWeight);m_pWeight=newint[m_nNumber+1];m_pValue=newint[m_nNumber+1];m_pWeight[0]=0;//读入每个物品的重量for(inti=1;i=m_nNumber;i++)fscanf(fp,%d,m_pWeight+i);m_pValue[0]=0;//读入每个物品的价值for(i=1;i=m_nNumber;i++)fscanf(fp,%d,m_pValue+i);//初始化每个物品被选中次数为0m_pCount=newint[m_nNumber+1];for(i=0;i=m_nNumber;i++)m_pCount[i]=0;fclose(fp);}CBeibao::~CBeibao(){delete[]m_pWeight;m_pWeight=NULL;delete[]m_pValue;m_pValue=NULL;delete[]m_pCount;m_pCount=NULL;}/*************************************************************************动态规划求出满足最大载重量的最大价值*参数说明：n:物品个数*m:背包载重量*w:重量数组*v:价值数组*c:是否被选中数组*返回值：最大价值************************************************************************/intCBeibao::GetMaxValue(intn,intm,int*w,int*v,int*c){introw=n+1;intcol=m+1;inti,j;//循环变量:前i个物品能够装入载重量为j的背包中//value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值int**value=newint*[row];for(i=0;irow;i++)value[i]=newint[col];//初始化第0行for(j=0;jcol;j++)value[0][j]=0;//初始化第0列for(i=0;irow;i++)value[i][0]=0;//计算for(i=1;irow;i++){for(j=1;jcol;j++){//w[i]j,第i个物品不装入背包value[i][j]=value[i-1][j];//w[i]=j,且第i个物品装入背包后的价值value[i-1][j],则记录当前最大价值inttemp=value[i-1][j-w[i]]+v[i];if(w[i]=j&&tempvalue[i][j])value[i][j]=temp;}}//逆推求装入的物品j=m;for(i=row-1;i0;i--){if(value[i][j]value[i-1][j]){c[i]=1;j-=w[i];}}//记录最大价值intnMaxVlaue=value[row-1][col-1];//释放该二维数组for(i=0;irow;i++){delete[col]value[i];value[i]=NULL;}delete[]value;value=NULL;returnnMaxVlaue;}intCBeibao::GetMaxValue(){intnValue=GetMaxValue(m_nNumber,m_nMaxWeight,m_pWeight,m_pValue,m_pCount);m_nMaxValue=nValue;returnnValue;}//显示结果voidCBeibao::Display(intnMaxValue){printf(%d\n,nMaxValue);for(inti=1;i=m_nNumber;i++){if(m_pCount[i])printf(%d%d\n,i,m_pCount[i]);}printf();}voidCBeibao::Display(intnMaxValue,constchar*filename){FILE*fp=fopen(filename,w);if(fp==NULL){printf(cannotwritefile!);return;//exit(0);}fprintf(fp,%d,nMaxValue);for(inti=1;i=m_nNumber;i++){if(m_pCount[i])fprintf(fp,%d%d,i,m_pCount[i]);}fclose(fp);}//显示菜单voidshow_menu(){printf(inputcommandtotesttheprogram\n);printf(iorI:inputfilenametotest\n);printf(qorQ:quit\n);printf($inputcommand);}voidmain(){charsinput[10];charsfilename[FILENAMELENGTH];show_menu();scanf(%s,sinput);while(stricmp(sinput,q)!=0){if(stricmp(sinput,i)==0){printf(pleaseinputafilename:);scanf(%s,sfilename);//获取满足最大载重量的最大价值CBeibaobeibao(sfilename);intnMaxValue=beibao.GetMaxValue();if(nMaxValue){beibao.Display(nMaxValue);intnlen=strlen(sfilename);strcpy(sfilename+nlen-4,_result.txt);beibao.Display(nMaxValue,sfilename);}elseprintf(error!pleasechecktheinputdata!);}//输入命令printf($inputcommand);scanf(%s,sinput);}}