背包问题总结.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,背包问题总结,2006,年,10,月,作业题,设有,n,件物品,重量分别为,w1,w2,w3,.,wn,和一个能装载总重量为,T,的背包,.,能否从,n,件物品中选择若干件恰好使它们的重量之和等于,T.,只需判断有解,.,搜索法,将解空间表示成树,同学们举了很多穷举,递归,回朔的算法,本质上都是用不同的方式遍历这个解空间树,.,解空间,设,Xi,表示第,i,件物品的取舍，,1,代表取，,0,代表舍，搜索的空间为,n,元一维数组（,X1,X2,X3,，,Xn,）,取值范围为（,0,，,0,，,0,，,0,，,0,），（,0,，,0,，,0,，,0,，,1,），（,0,，,0,，,0,，,1,，,0,），（,0,，,0,，,0,，,1,，,1,），,，（,1,，,1,，,1,，,1,，,1,）。,解空间图示,以,3,个物品为例,解,(0,1,0),表示,(,不取物品,0,取物品,1,不取物品,2),root,0,1,0,1,0,1,0,1,0,求解背包问题就变成搜索这棵数,.,下面列举,.,只列出常见的方法,方法,1,算法描述,:,访问结点,访问左子树,访问右子树,实现,bool,test(v,t)/v,为当前物品编号,t,为背包剩余容量,/,测试当前节点,if(t,=0)return true;,if(t,=n)return false;,if(t,0),if(!test(v+1,t)/,访问左子树,&!test(v+1,t-weightv)/,访问右子树,return false;,return true;,方法,2,方法,2,是同学们使用较多的一种方法,.,思路,:,按编号从小到大取物品,解空间被分解为,n,个子集,s(1),s(2),s(i,).,s(i,),表示按从小到大顺序取物品,所取第一个物品编号为,i,的取法,.,s(i,)0,则表示有解,.,实现,.,bool,test(I,t,)/i,为当前物品编号,t,为背包剩余容量,if(t,=0)return true;,for(j,=,i;j,N;j,+),if(,test(j,t-weightj,),return true;,return false;,3.,遍历这个树,2.,遍历这个树,1.,遍历这个树,它遍历这棵树的方法如下所示,:,root,0,1,0,1,0,1,0,1,.,上面列举的都是递归的算法,其他还有一些非递归的算法本质上都是遍历这棵树不再列举,.,动态规划法,递推方程,:,设,F(n,t,),表示用前,n,种物品装容量为,t,的背包的方法数,则,F(n,t,)=F(n-1,t)+F(n-1,t-w(n),F(n,0)=1,F(0,t)=0,F(n,x)=0,当,x0,表示有解,当物品重量,背包容量为整数时,子问题重复程度较高,可减少算法的复杂度,.,当重量和背包容量为小数时,效率会受影响,并不是有的同学说的不能用动态规划求解,这时可用一个,STL,的,map,来记录状态,算法效率与子问题的重复程度有关,具体实现时,可以选择递归算法和非递归算法,递归算法重复的子问题会重复计算,动态规划法,实例,w=5,3,1,2,7,T=8,F(n,t,)=F(n-1,t)+F(n-1,t-w(n),F(5,8)=F(4,8)+F(4,1),F(4,1)=F(3,1)+F(3,-1)=1,F(3,1)=F(2,1)+F(2,0)=1,F(2,1)=F(1,1)+F(1,-2)=0,F(1,1)=0,F(1,-2)=0,F(2,0)=1,F(3,-1)=0,F(4,8)=F(3,8)+F(3,6),F(3,8)=F(2,8)+F(2,7),F(2,8)=F(1,8)+F(1,5)=1,F(3,6)=F(2,6)+F(2,5),算法实现,递归算法,:,F(n,t,)/,用前,n,种物品,填充容量,t,的方法数,if(t,=0)return 1/,若,t,是小数,则改为,abs(t-0)0.0001,if(t,0)return 0,if n=0 return 0,return F(n-1,t)+F(n-1,t-Wn),算法实现,非递归算法,F(T),map m;,m0=1/,背包容量为,0,for(i,=0;ifirst,mt+Wi,=1,if,t+Wi,=T,return true,贪心法,有些同学尝试用贪心法解决此题,却没有说明贪心法有可能得不到最优解,需要注意,.,本题并不满足贪心性质,.,下面的小数背包问题可以用贪心法来解决,.,扩展,加入物品价值的概念,物品可分割,物品不可分割,物品可多选,扩展,1,加上物品价值,从,n,个物品中选取若干物品装载容量为,M,的背包；已知：第,i,个物品的重量是,wi,，价值是,pi(i,=1,2,n),且每个物品是无法分割的。求：最后装载方案，即总重量小于,M,总价值最大,错误方法,:,贪心法,思路,:,将物品按照价值,/,重量的比值排序,优先选择比值大的物品,.,举例,:,物品,(,价值,重量,):(3,1),(2,1)(2,1),限重,:4,如果采用贪心法,只能取第一个元素得到的价值为,3,实际上应该取第,2,和第,3,个元素得到的价值为,4,原因是,:,物品不可分割,导致背包不能装满,降低了前面选择的效用,.,扩展,1,加上物品价值,思路,1:,搜索法,举例,:V=12,11,9,8,W=8,6,4,3,T=13,解向量,:,解空间树,root,1,0,1,0,1,0,1,0,对应于可行解,x1=1,x2=0,x3=1,x4=0,重量,:13,价值,28,搜索法,算法就是搜索整个解空间树,比较所有可行解得到最优解,.,思路,2:,动态规划法,后面的扩展,3,再谈,扩展,2-,物品可以任意分割,设有,n,件物品，重量分别为,w1,w2,w3,wn,，价值分别为,v1,v2,v3,vn,和一个能装载总重量为,T,的背包。能否从,n,件物品中选择若干件装在背包中，使背包中物品的总价值最大。（物品可以被任意分割）,扩展,2-,物品可以任意分割,思路,:,贪心法,按价值重量比对物品排序,优先选择比值大的物品,.,对于第,i,个物品，若,wi,小于所剩能容纳的重量，取全部的,i,物品，若,wi,大于所剩能容纳的重量，取所剩能容纳的重量,T,的,i,物品，此时整个选择结束。,扩展,3-,物品可多选,思路,:,动态规划法,设,F(k,y,),表示只用前,k,种物品,背包总重不超过,y,时背包的最大价值,递归方程与边界条件,F(k,y,)=maxF(k-1,y),F(y-w(k)+v(k),F(0,y)=0,F(k,0)=0,F(1,y)=|y/w(1)|*V(1),总结,这次作业总体情况良好,很多同学应用多种算法解决了教材上的背包问题,.,另外,还收集了一些其他种类的背包问题,.,思路灵活,思维发散,态度认真,.,几个注意点,:,文档描述更清楚点,不要只贴代码,.,要配合算法,讲解自己的思路,.,说明自己应用的算法类型,方便助教批改作业,.,代码中的注释适当多一点,变量命名要和题意结合,要有意义,.,变量的作用要说明,不要一堆,I,j,k,m,n,而不说明作用,.,上传的文件里不要包含可执行程序,压缩包太大,.,程序要有,Makefile,文件或者,VC,工程文件,不要只有单独的源程序,方便助教编译,.,未收到下列同学的作业,王 璐,00548261,王 媛,00548097,-,杨磊,00548101,宋辰,00548144,李春,00548170,冯熙铉,00548217,赵铉,00348239,韦伟,00448327,那春雷,00548229,