《0-1背包问题四种不同算法的实现》由会员分享，可在线阅读，更多相关《0-1背包问题四种不同算法的实现（41页珍藏版）》请在金锄头文库上搜索。
1、兰州交通大学数理与软件工程学院题 目 -背包问题算法实现院 系 数理院 专业班级 信计09 学生姓名 雷雪艳 学 号 0510 指引教师 李秦 六月五 日一、问题描述： 1、0背包问题：给定n种物品和一种背包,背包最大容量为M，物品i的重量是wi,其价值是平i,问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大?背包问题的数学描述如下:2、规定找到一种n元向量(x1,xn),在满足约束条件:状况下，使得目的函数,其中,1n;M0;0;pi0。满足约束条件的任何向量都是一种可行解,而使得目的函数达到最大的那个可行解则为最优解1。 给定n种物品和1个背包。物品 的重量是wi,其价值为pi
2、,背包的容量为M。问应如何装入背包中的物品,使得装人背包中物品的总价值最大?在选择装人背包的物品时，对每种物品只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次,也不能只装入部分的物品i。该问题称为0-1背包问题。-背包问题的符号化表达是,给定M, wi ， ,1n，规定找到一种n元0-1向量向量(x1，x2n)， Xi =0或1, in, 使得 ，并且达到最大2。二、解决方案：方案一：贪心算法1、贪心算法的基本原理与分析 贪心算法总是作出在目前看来是最佳的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最
3、优解,但对范畴相称广的许多问题它能产生整体最优解。在某些状况下,虽然贪心算法不能得到整体最优解,但其最后成果却是最优解的较好近似解。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子构造性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一种基本要素,也是贪心算法与动态规划算法的重要区别。当一种问题的最优解涉及其子问题的最优解时,称此问题具有最优子构造性质。问题的最优子构造性质是该问题可用动态规划算法或贪心算法求解的核心特性。2、-1背包问题的实现对于背包问题,设是能装入容量为c的背包的具有最大价值的物品集合，则A=j是
4、-1个物品,2,.,-1,j+,.,n可装入容量为w的背包的具有最大价值的物品集合。用贪心算法求解0-1背包问题的环节是,一方面计算每种物品单位重量的价值vi；然后，将物品进行排序，依贪心选择方略,将尽量多的单位重量价值最高的物品装入背包。若将这种物品所有装入背包后，背包内的物品总量未超过,则选择单位重量价值次高的物品并尽量多地装入背包。依此方略始终进行下去,直到背包装满为止。3、算法设计如下：#nlue#define mx 10 /最多物品数voi sor(intn,lat amx,foa bmax) /按价值密度排序t j，h，k;foa t1，2，t,mx;for(k=;；k+)ck=k
5、/k；r(j=0;j+)i(cjcj1)t=j;aj=j+1;aj1=t1;2=bj;bj=bj+;b+1=t2;=cj;cjj+1；j+1=t3;oi napsc（in n,flotliitw,foat vmax，floatm,in max)floa c1； /c为背包剩余可装载重量inti;ot(n，v,）; /物品按价值密度排序c1litw；for(i=0;ic1)a;xi=1； /为时,物品i在解中c1=c-;oid an()t ，,xax;fla vmax,wm,alv0,totalw=0，limitw；oun limiw；for（i=;i=n;i+)xi=0; /物品选择状况表初始
6、化为0cot请依次输入物品的价值：d;f(i=1;ivi;uendl;co请依次输入物品的重量：wi；otel;knapsac (,limitw,w,x）;coutthe elction i:;fr(i=1;i=n;+）coutx;if(x=1）total=ttlww;totav=tav+vi；cotend；co背包的总重量为：toawedl; /背包所装载总重量cout背包的总价值为:totalvdl； /背包的总价值4、贪心算法运营成果如下图所示：方案二：动态规划算法1、动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题,然后从这些子问题的解得到原
7、问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果可以保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量反复计算,从而得到多项式时间算法。它把已知问题分为诸多子问题，按顺序求解子问题，在每一种状况下，列出多种状况的局部解，按条件从中选用那些最有也许产生最佳的成果舍弃其他。前一子问题为背面子问题提供信息，而减少计算量，最后一种子问题的解即为问题解。采用此措施求解0-1背包问题的重要环节如下:分析最优解的构造:最有子构造性质;建立递归方程;计算最优值；构造最优解4。2、0-1背包问题的实现 最优子构造性质-1背包问题具有最优子构造性质。
8、设(y1，y2y）是所给0-1背包问题的一种最优解,则(y2,y3yn)是下面相应子问题的一种最优解:因若否则，设(z2,z3z）是上述问题的一种最优解，而（2,3yn）不是它的最优解,由此可见,且c。因此c这阐明(y1,z2zn)是所给-1背包问题的一种更优解，从而(1，yyn)不是所给0-背包问题的最优解。此为矛盾。递归关系设所给0-背包问题的子问题 的最优值为m(,)，即(i，j)是背包容量为j，可选择物品为i,i+1,时0-1背包问题的最优值。由1背包问题的最优子构造性质,可以建立计算m(i,)的递归式如下:3、算法设计如下：inlud#includeusing amespacestd
9、;const in MAX=0;intwAX,M，bestMX;int VAXMX; /最大价值矩阵t W，; /W为背包的最大载重量，为物品的数量/求最大值函数int ax(it ,in y) turx= y?x:;/求最小值函数int n(it x，nt y）return x= y？ y:x；void napack（)in Mamin(n1,W); for(int j1;j Max ; j+)Vnj0;o( =wn; j 1 ;i-)Ma=min(w-1，W）;for( =1； j = Ma; +)Vij=V1j；for( j=w;j w) V1Wma(1W，V2W-w1+v1）;/生成向
10、量数组，决定某一种物品与否应当放入背包vd Traback()or(int =1; i ;i+) /比较矩阵两邻两行(除最后一行)，背包容量为的最优值.if(ViW = V+1W) /如果目前行的最优值与下一行的最优值相等,则表白该物品不能放入。esti=0;ese 否则可以放入besti=1;W-wi;besn=(Vn )?：0；oid m() outnW;o输入每件商品的重量：w；me（V,0,sizeo（V)）；out输入每件商品的价值v:enl;fr( i=1;vi;Knspak（）;/构造矩阵 Taeack(); /求出解的向量数组n ttl=0;nt otal=0;/显示可以放入的物品cu所选择的商品如下:enl;out序号:重量:价格v：l;or(i=1;i = ； i+)if(beti = 1)toaW=wi;totaV+v;ouseiosfgs(ios:left)setw（5)i wi ien;cou放入的物品重量总和是:ttalW 价值最优解是：V1W totalVendl;4、计算复杂性分析运用动态规划求解-背包问题的复杂度为（mnn,2n。动态规划重要是求解最优决策序列，当最优决策序列中涉及最优决
