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

0/1背包问题1. 问题描述给定一个载重量为m，n个物品，其重量为wi，价值为vi，1=ij，第i个物品不装入背包 否则，若wivaluei-1j，则记录当前最大价值（替换为第i个物品装入背包后的价值） 计算最大价值的动态规划算法如下：/计算for(i=1;irow;i+)for(j=1;jj,第i个物品不装入背包valueij=valuei-1j;/wivaluei-1j,则记录当前最大价值inttemp=valuei-1j-wi+vi;if(wivalueij)valueij=temp; 即该段程序完成以下n个阶段： 1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值 2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值 。 n：以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值3. 问题求解 确定装入背包的具体物品，从valuenm向前逆推： 若valuenmvaluen-1m，则第n个物品被装入背包，且前n-1个物品被装入载重量为m-wn的背包中 否则，第n个物品没有装入背包，且前n-1个物品被装入载重量为m的背包中 以此类推，直到确定第一个物品是否被装入背包为止。逆推代码如下：/逆推求装入的物品j=m;for(i=row-1;i0;i-)if(valueijvaluei-1j)ci=1;j-=wi;4. 代码如下 输入数据及输出数据均在文件中。 输入数据格式： n m w1w2. wn v1 v2 . vn 输出数据格式： maxValue i count /i表示物品编号，count表示该物品被选中次数 ./*0/1背包问题求解(visualstudio2005)*给定一个载重量为m,及n个物品,其重量为wi,价值为vi,1=i=n*要求:把物品装入背包,并使包内物品价值最大*/#include#include#include#defineFILENAMELENGTH100classCBeibaopublic: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=newintm_nNumber+1;m_pValue=newintm_nNumber+1;m_pWeight0=0;/读入每个物品的重量for(inti=1;i=m_nNumber;i+)fscanf(fp,%d,m_pWeight+i);m_pValue0=0;/读入每个物品的价值for(inti=1;i=m_nNumber;i+)fscanf(fp,%d,m_pValue+i);/初始化每个物品被选中次数为0m_pCount=newintm_nNumber+1;for(inti=0;i=m_nNumber;i+)m_pCounti=0;fclose(fp);CBeibao:CBeibao()deletem_pWeight;m_pWeight=NULL;deletem_pValue;m_pValue=NULL;deletem_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的背包中/valueij表示前i个物品能装入载重量为j的背包中物品的最大价值int*value=newint*row;for(i=0;irow;i+)valuei=newintcol;/初始化第0行for(j=0;jcol;j+)value0j=0;/初始化第0列for(i=0;irow;i+)valuei0=0;/计算for(i=1;irow;i+)for(j=1;jj,第i个物品不装入背包valueij=valuei-1j;/wivaluei-1j,则记录当前最大价值inttemp=valuei-1j-wi+vi;if(wivalueij)valueij=temp;/逆推求装入的物品j=m;for(i=row-1;i0;i-)if(valueijvaluei-1j)ci=1;j-=wi;/记录最大价值intnMaxVlaue=valuerow-1col-1;/释放该二维数组for(i=0;irow;i+)deletecolvaluei;valuei=NULL;deletevalue;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,nMaxValue);for(inti=1;i=m_nNumber;i+)if(m_pCounti)printf(%d%d,i,m_pCounti);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);voidmain()charsinput10;charsfilenameFILENAMELENGTH;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);5. 运行结果如下文件中的内容如下：1. input.txt 4 10 2 3 4 7 1 3 5 9 input_result.txt 12 2 1 4 12. input1.txt 5 10 2 2 6 5 4 6 3 5 4 6 input1_result.txt 15 1 1 2 1 5 1 3. input2.txt 5