背包问题(动态规划法).docx

0/1背包问题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;i<row;i++){for(j=1;j<col;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&&temp>value[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;i>0;i--){if(value[i][j]>value[i-1][j]){c[i]=1;j-=w[i];}}4.代码如下输入数据及输出数据均在文件中。输入数据格式：nmw1w2...wnv1v2...vn输出数据格式：maxValueicount//i表示物品编号，count表示该物品被选中次数.../*************************************************************************0/1背包问题求解(visualstudio2005)*给定一个载重量为m,及n个物品,其重量为wi,价值为vi,1<=i<=n*要求:把物品装入背包,并使包内物品价值最大************************************************************************/#include<stdio.h>#include<stdlib.h>#include<string.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(inti=1;i<=m_nNumber;i+