蛮力法等求解背包问题报告剖析

1、算法综合实验报告学号：姓名：一、实验内容：分别用蛮力、动态规划、贪心及分支限界法实现对TSP问题或者0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设计的基本思想、原理和算法描述：1、蛮力法(1)数据结构:使用一维数组存储物品的价值和重量还有下标。(2)函数组成除主函数外还有一个subset()函数，在此函数中列出所有的子集列出子集的同时求解最大价值，并且物品总重量要小于背包总容量。(3) 输入/输出设计首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。最后输出物品的最

2、大价值。本程序通过键盘进行输入、屏幕进行输出。(根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式)(4) 符号名说明w1001为物品重量的集合，v1001为物品价值的集合，n为物品数量，m为背包总容量,x1001用来存储物品是否装入背包，0为不装入，1为装入。用a1001来存储下标，用下标找出所有子集。(5) 算法描述采用增量构造的方法来构造出物品的所有子集，对物品的下标应用此方法进行构造，下标与物品相对应，选出子集时物品的重量加之前重量小于背包总重量时将价值加上去，最后选出能装入背包的物品的最大值。2、动态规划法(1)数据结构：使用一维数组存储各个物品价值，重量，

3、使用一个二维数组存储动态规划的整体求解的表，并以背包容量为最大列号，物品个数为最大行号。(2)函数组成：除主函数外由两个函数组成，一个是求解两个数中的大的一个的函数，另一个则是进行动态规划求解的函数，在使用动态规划方法具体求解时调用求最大值函数，在主程序之中调用动态规划函数。(3)输入/输出设计：首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。输出物品的最大价值。本程序通过键盘进行输入、屏幕进行输出。(根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式)(4)符号名说明：w1001为物品

4、重量的集合,1001为物品价值的集合，为物品数量，m为背包总容量,x1001用来存储物品是否装入背包，0为不装入，1为装入。V10011001用来存储动态规划具体求解过程,Vnm为最终结果最大价值。(5)算法描述：1 .背包容量不足以装入物品i,则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，则xi=0，背包不增加价值。2 .背包容量可以装入物品i,如果把第i个物品装入背包，则背包中物品的价值等于前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值；如果第i个物品没有装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j的背包中所取得的价值。取二者

5、中价值较大者作为把前i个物品装入容量为j的背包中的最优解。Vj)表示在前i-i-n)个物品中能够装入容量为j(1-j-C)的背包中的物品的最大值，则可以得到如下动态函数：V(i,0)二V(0,j)二0IV(i-1,j)(jw)V(i,j)二丿八丿/)maxV(i-1,j),V(i-1,j-w)+vw)iii3、贪心法(1)数据结构：定义多个一维数组存储数据进行贪心选择。(2)函数组成：编写了一个选择排序函数，一个判断是否能装入包中的函数，一个主函数，在主函数中调用判断函数，在判断函数初始调用排序函数将单位价值重量从大到小进行排序。(3) 输入/输出设计：首先通过键盘输入物品的总重量，再输入背包

6、总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。先输出放入背包中的物品序号，在输出总价值，最后输出背包总容量。本程序通过键盘进行输入、屏幕进行输出。(根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式)(4) 符号名说明:w1001为物品重量的集合，v1001为物品价值的集合，a1001为单位物品价值集合,n为物品数量，m为背包总容量,x1001用来存储物品是否装入背包，0为不装入，1为装入。(5)算法描述：制定贪心策略，求出单位物品价值并从大到小进行排序，依照排序结果从大到小放入，知道物品重量大于背包剩余容量为止，但是求出的

7、并不是最优解，贪心法无法求出0/1背包的最优解，只能求出背包问题的最优解。4、分支限界法(1)数据结构定义一个优先队列存储分支限界所使用的树的节点，使用一维数组存储物品的重量和价值。(2)函数组成一个构造函数，申请动态数组构造树，一个析构函数，删掉动态申请的数组，一个计算上界的函数，一个生成新节点的函数，一个将节点加入优先队列的函数，一个取上界最大节点的函数，一个背包问题求解的函数，一个显示函数，在主函数中调用函数求解。本程序还使用了类和结构体。(3)输入/输出设计通过键盘先输入背包总容量，再输入物品总数，依次输入每个物品的重量，依次输入每个物品的价值。输出最大价值以及每个物品是否装入背包中本

8、程序通过键盘进行输入、屏幕进行输出。(根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式)(4)符号名说明Cw为当前背包装载量，cv为当前背包价值，ub节点的上界值，c为背包的容量，n为物品数量，x记录物品是否放入背包，0为不放入，1为放入，w为存放物品重量的数组，v为存放物品价值的数组。(5)算法描述给定n种物品和一个容量为C的背包，物品i的重量是Wi,其价值为Vi,0/1背包问题是如何选择装入背包的物品(物品不可分割),使得装入背包中物品的总价值最大，一般情况下，解空间树中第i层的每个结点,都代表了对物品1i做出的某种特定选择，这个特定选择由从根结点到该结点的路径

9、唯一确定:左分支表示装入物品,右分支表示不装入物品。对于第i层的某个结点，假设背包中已装入物品的重量是w,获得的价值是v,计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v,加上背包剩余容量W-w与剩下物品的最大单位重量价值vi+1/wi+1的积,于是,得到限界函数:ub=v+(W-w)X(vi+1/wi+1)根据限界函数确定目标函数的界down,up，然后，按照广度优先策略遍历问题的空间树。三、源程序及注释：1、蛮力法#include#includeusingnamespacestd;intx1001=0;intw1001,v1001;intmaxValue=0;in

10、tsubset(intn,intm,int*A,intcur)/n是数组长度,A为待求子集数组，cur用于递归记录intweight=0;intvalue=0;for(inti=0;icur;i+)/这个用于输出子集/printf(%d,Ai);if(weight+wAim)xAi=1;weight=weight+wAi;value=value+vAi;if(maxValuevalue)maxValue=value;/printf(n);ints=cur?AcurT+1:0;/判断cur是否是0,避免越界，是0的话就取s=0,非零的话s=Acur-1for(i=s;in;i+)/递归构造子集A

11、cur=i;subset(n,m,A,cur+1);returnmaxValue;intmain()intn,m;inta1000;cout请输入物品总数量:endl;cinn;/输入物品总数量cout请输入背包总容量:m;/输入背包总容量cout请依次输入物品的重量和价值endl;for(inti=0;iwi;cinvi;ai=i;/记录下标cout总价值为:subset(n,m,a,0)endl;return0;2、动态规划法#include#includeusingnamespacestd;intV10021002;intw1001,v1001;intmax(intxx,intyy)/判

12、断两个数谁大，返回大的那个值if(xx=yy)returnxx;elsereturnyy;intKnapSack(int*w,int*v,intn,intm)intx1001=0;inti,j;for(i=0;i=n;i+)/初始化第0列为0Vi0=0;for(j=0;j=m;j+)/初始化第0行为0V0j=0;for(i=1;i=n;i+)/在背包能放下的情况下，如果放入后比i-1个物品装入后价值还小则不放入for(j=1;j=m;j+)/计算第i行，进行第i次迭代if(j0;i-)/求装入背包的物品if(VijVi-1j)xi=1;j=j-wi;elsexi=0;returnVnm;/返回

13、背包取得的最大价值intmain()intn,m;/n为物品数量，m为背包容量inti;intmaxValue;cout请输入物品数量n;cout请输入背包容量m;cout请依次输入每个物品的重量和价值(注：重量在前，价值在后)endl;for(i=1;iwi;cinvi;maxValue=KnapSack(w,v,n,m);cout最大价值是：maxValueendl;return0;3、贪心法：#include#includeusingnamespacestd;intn,m;intw1001,v1001;doublea1001;intmaxValue=0;intb1001;/存储物品序号i

14、ntx1001=0;/0为不放入背包，1为放入背包voidSort(intn,double*a,int*w,int*v,int*b)/排序函数for(inte=0;ee;t-)if(aeat)inttemp=ae;intq=we;ints=ve;intp=be;ae=at;at=temp;we=wt;wt=q;ve=vt;vt=s;be=bt;bt=p;intKnapSack(intn,intm,int*w,int*v,int*x)/判断是否能装入背包Sort(n,a,w,v,b);for(intj=0;wjn;/输入物品总个数cinm;/输入背包总容量intweight=0;for(inti

15、=0;iwi;/输入物品重量cinvi;/输入物品价值ai=vi/wi;/求得单位重量价值bi=i+1;/记录物品序号maxValue=KnapSack(n,m,w,v,x);for(intj=0;jn;j+)if(xj=1)cout第bj个物品装入；weight=weight+wj;coutendl；coutmaxValueendl；/输出能装入的总价值cout总重量为：weightendl;return0;5、分支限界法#include#includeusingnamespacestd;int*x;structnodenode*parent,*next;intlevel,bag,cw,cv

16、;floatub;/结点表结点数据结构/父结点指针/后继结点指针/结点的层/节点的解/当前背包装载量/当前背包价值/结点的上界值cv);/计算上界,floatuub);/生成一个结点ba=1生/将结点添加到队列中/将结点队列中删除/取下一个节点/输出结果/背包问题求解nn)/构造函数classKnapprivate:structnode*front,/队列队首*bestp,*first;/解结点、根结点int*v,*w,n,c,*M;/背包价值、重量、物品数、背包容量、记录大小顺序关系longIbestp;/背包容量最优解public:voidSort();Knap(int*pp,int*ww

17、,intcc,intnn);Knap();floatBound(inti,intcw,innode*nnoder(node*pa,intb成左节点ba=0生成右节点voidaddnode(node*nod);voiddeletenode(node*nod);structnode*nextnode();voiddisplay();voidsolvebag();Knap:Knap(int*pp,int*ww,intcc,intinti;n=nn;c=cc;/动态申请数组v=newintn;w=newintn;M=newintn;for(i=0;inext=NULL;lbestp=0;bestp=n

18、ewnode1;bestp=NULL;Sort();Knap:Knap()/析构函数deletefirst;deletefront;deletebestp;deletev;deletew;floatKnap:Bound(inti,intcw,intcv)/计算上界intleft=c-cw;floatb=(float)cv;while(in&wi=left)left-=wi;b+=vi;i+;if(iparent=pa;nodell-next=NULL;nodell-level=(pa-level)+1;nodell-bag=ba;nodell-ub=uub;if(ba=1)nodell-cw=

19、pa-cw+wpa-level;nodell-cv=pa-cv+vpa-level;elsenodell-cw=pa-cw;nodell-cv=pa-cv;return(nodell);voidKnap:addnode(node*no)优先队列node*p=front-next,*next1=front;floatub=no-ub;while(p!=NULL)if(p-ubnext=p;next1-next=no;break;next1=p;p=p-next;if(p=NULL)next1-next=no;node*Knap:nextnode()大结点node*p=front-next;fro

20、nt-next=p-next;return(p);voidKnap:Sort()inti,j,k,kkl;floatminl;for(i=1;in;i+)minl=1.0*vi/wi;k=0;/将结点加入/取上限最for(j=1;j=n-i;j+)if(minl1.0*vj/wj)minl=1.0*vj/wj;swap(vk,vj);swap(wk,wj);swap(Mk,Mj);k=j;voidKnap:display()/显示函数inti;cout最大价值是：lbestp=1;i-)xMi-1=bestp-bag;bestp=bestp-parent;cout物品状态为(0为不装入，1为装

21、入)：endl;for(i=1;i=n;i+)coutx(i)=xi-1parent=NULL;first-next=NULL;first-level=0;first-cw=0;first-cv=0;first-bag=0;ubb=Bound(0,0,0);first-ub=ubb;front-next=first;while(front-next!=NULL)aa=nextnode();i=aa-level;if(i=n-1)if(aa-cw+wicv+vi)lbestp)lbestp=aa-cv+vi;bestp=nnoder(aa,1,(float)lbestp);if(long)(aa

22、-cv)lbestp)lbestp=aa-cv;bestp=nnoder(aa,0,(float)lbestp);if(icw+wicw+wi,aa-cv+vi)(float)lbestp)ubb=Bound(i,aa-cw+wi,aa-cv+vi);addnode(nnoder(aa,1,ubb);ubb=ubb=Bound(i,aa-cw,aa-cv);if(ubblbestp)addnode(nnoder(aa,0,ubb);display();voidmain()intc,n;inti=0;int*v;int*w;cout请输入背包容量:c;cout请输入物品数：n;x=newintn

23、;v=newintn;w=newintn;cout请输入n个物品的重量：endl;for(i=0;iwi;cout请输入n个物品价值：endl;for(i=0;ivi;x=newintn;Knapknbag(v,w,c,n);knbag.solvebag();return;四、运行输出结果：1、蛮力法测试1：测试2：2、动态规划法测试1：测试2：3、贪心法：测试1：4、分支限界法测试1：请输人背包容量:10请输入物品数：舊输入4个物品的重量：734请输入4个物品价值：42L240翳嫖魚爲不装入丄为装入：K=0K=0k=1k=1Pressanykeytocontinue：170大态为個为不装入,

24、丄为装入冃砸八冃巴召J青输入物品数:*ressanykeytocontinue=1=1=0五、调试和运行程序过程中产生的问题及采取的措施：输入=个物品的重量：3010输入3个物品价值：120501、在传数组时一开始就是在报错，最后我使用了全局变量定义数组，使用了指针直接传指针，eg:max(a,b),a,b,是数组，定义函数时voidSort(intn,double*a,int*w,int*v,int*b)才可以进行。错误如下图：2、写动态规划法程序时，参照书上思想进行编程结果总是错误，因为我定义Vn+1m+1，所以在main中传入重量和价值时应该从i=1开始到i二n为止才是正确的。3、在写蛮

25、力法求解0/1背包问题的时候一开始不知道怎么列出所有子集，后来询问同学知道了增量构造的方法才解出的。4、蛮力法求解时解总是不对后来我发现我将weight和value设为全局变量后只赋了一次0，必须在蛮力法求解的函数之前清零，否则重量与价值都在不断累加。5、在写分支限界法时一开始觉得算法的思想很简单，就是以广度优先来遍历一棵树，通过限界函数不断剪枝，并以值的大小用优先队列进行存储，但是实际实践时就出现了很多问题，最后是通过询问同学与同学一起讨论加上上网搜集一些资料才解出的。六、对算法的程序的讨论、分析，改进设想，其它经验教训：1、贪心法求解01背包问题无法得到最优解，蛮力法，动态规划法，分支限界

26、法都能求解出最优解。2、使用分支限界法的时候遇到了许多的问题，此方法要用对或者优先队列来存储节点，但是我本身对堆和队列的掌握就不是特别的好，所以进行了复习，重新看了队列的使用最终使用优先队列实现了此代码。3、蛮力法求解时时间复杂度为0(2八n),动态规划法的时间复杂度为0(n*c),贪心法因为无法求解出最优解时间复杂度无意义，分支限界法无法确定具体时间复杂度，只能知道最好和最坏的。4、贪心法求解背包问题可以取得最优解。5、对于分支限界法既可以用堆也可以用队列，而我在本次实验中使用了队列，下去后我会找机会使用堆来再编写此程序。6、这是在使用动态规划时一开始输入i=0,in时的结果，但是明明应该是

27、错的因为我的数组是Vn+1Wn+1可是结果却是对的这一点令我感觉非常的奇怪，目前还不知道具体的原因，会进一步去我寻找问题的答案，去考虑为什么原本应该是错误的答案最后却异常的正确了，会课下再进行研究。7、我后来再改进重新运行贪心法求解01背包问题时发现传数组可以不用*w或*v可以直接使用voidSort(intn,doublea1001,intw1001,intv1001,intb1001)，这样也可以实现数组的值得传递，调用时maxValue二KnapSack(n,m,w,v,x);这样就可以实现在调用时传递数组的值。8、使用蛮力法求解01背包问题时主要是求出物品的所有子集，在这个问题上我也花费了非常多的时间，开始也不知道怎么去下手，后来经过和同学的讨论以及自己的思考才使用了此报告中的思想，中间花费了很长的时间去研究，不过听说还有很多种求解子集的方法，好像还有二进制求解之类的，这个在课后