第四讲：背包问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四讲 背包问题,1,、问题描述,给定一组物品，每种物品都有自己的重量和价格,(,价值,),，在限定的总重量范围内，我们如何选择，才能使得物品的总价值最高。,问题名称的来源,人类是一种贪婪的动物，如果给您一个容量一定的背包和一些大小不一的物品，裝到背包里面的物品就归您，遇到这种好事大家一定不会错过，用力塞不一定是最好的办法，用脑子才行。,另一个版本：人类是一种贪婪的动物，如果给您一些重量不一、价值不一的物品，只要您一次性扛得走就归您。,问题的抽象化,已知背包容量为,w,，,n,件物品，物品的重量依次为,w,i,，物品的价格依次为,p,i,，如何选取一部分物品，使其重量之和不超过,w,，而价格之和最大。,2,、解决问题的自然思路,取不取第一件物品？,(,W,1,W,则显然不取,),假定取了第一件物品，则剩下的事情可以表述为：已知背包容量为,W(,即,W-W,1,),，,n-1,件物品，物品的重量和价格已知，如何选取一部分物品，使其重量之和不超过,W,，而价格之和最大。,(,以下简称为问题,A),假定不取第一件物品，则剩下的事情可以表述为：已知背包容量为,W,，,n-1,件物品，物品的重量和价格已知，,如何选取一部分物品，使其重量之和不超过,W,，而价格之和最大。,(,以下简称为问题,B),假定,A,问题已经解决，所选物品的价格之和为,P,A,；假定,B,问题已经解决，所选物品的价格之和为,P,B,。如果,P,A,+P,1,P,B,我们不取第一件物品，否则就取。,问题A、问题B与原来的问题性质完全相同，复杂度有所降低；再次分别展开这两个问题，性质也完全相同，复杂度再次降低；分解到最后，必然只有一件物品要考虑。,这启发我们，解决规模较大的问题，可以先分解，解决规模较小的问题；继而再分解，解决规模更小的问题；直到不需要再分解；然后回过头来解决之前的问题。这种思路被称之为“递归”,3,、类属性设计,问题领域有哪些对象,?,背包、物品,class Bag,class Thing,public class Thing,public final,int,weight;,public final,int,price;,public,Thing(int,weight,int,price),this.weight,=weight;,this.price,=price;,物品类,public class Bag,public final,int,capacity;,private Vector things=new Vector();,public,Bag(int,capacity),this.capacity,=capacity;,public,int,getTotalWeight,(),int,result=0;,for(int,i=0;i,things.size();i,+),result+=,things.get(i).weight,;,return result;,public,int,getTotalValue,(),int,result=0;,for(int,i=0;i=,thing.weight,;,private,boolean,isExist(Thing,thing),for(int,i=0;i W,则显然不取,),假定取了第一件物品，则剩下的事情可以表述为：已知背包容量为,W(,即,W-W,1,),，,n-1,件物品，物品的重量和价格已知，如何选取一部分物品，使其重量之和不超过,W,，而价格之和最大。,(,以下简称为问题,A),假定不取第一件物品，则剩下的事情可以表述为：已知背包容量为,W,，,n-1,件物品，物品的重量和价格已知，,如何选取一部分物品，使其重量之和不超过,W,，而价格之和最大。,(,以下简称为问题,B),假定,A,问题已经解决，所选物品的价格之和为,P,A,；假定,B,问题已经解决，所选物品的价格之和为,P,B,。如果,P,A,+P,1,P,B,我们不取第一件物品，否则就取。,解决方案,如果一件物品也没有，返回空的背包；,考虑取第一件物品，求解,A,问题，得到背包,bag1,；,考虑不取第一件物品，求解,B,问题，得到背包,bag2,；,如果,bag1,的总价格,+,第一件物品的价格,capacity)return,bagWithPrimitiveCapacity,;,/,求解,A,问题：不包括第一件物品，原始容量减去第一件物品重量,Bag,bagWithSmallCapacity,=,solution,(capacity,-,first.weight,cloneWithoutFirst(allThings,);,/,如果,PA+P1 PB,，返回,B,问题的解,if(,first.price,+,bagWithSmallCapacity.getTotalValue,(),bagWithPrimitiveCapacity.getTotalValue,(),return,bagWithPrimitiveCapacity,;,/,否则返回 第一件物品与,A,问题的解共同构成的解,return,createBagByFirstAndOthers(first,bagWithSmallCapacity,);,待完成,Bag,类添加,cloneWithoutFirst(Vector,allThings,),方法,private,static,Vector,cloneWithoutFirst(Vector,allThings,),if(,allThings.size,()=0),throw new Error(,参数错误：向量元素个数不能为零,);,Vector result=new Vector();,for(int,i=1;i,allThings.size();i,+),result.add(allThings.get(i,);,return result;,Bag,类添加,createBagByFirstAndOthers,方法,private static Bag,createBagByFirstAndOthers(Thing,first,Bag,bagWithSmallCapacity,),Bag,bagWithFirst,=new,Bag(bagWithSmallCapacity.capacity+first.weight,);,bagWithFirst.place(first,);,Vector,otherThings,=,bagWithSmallCapacity.things,;,for(int,i=0;i,otherThings.size();i,+),bagWithFirst.place(otherThings.get(i,);,return,bagWithFirst,;,准备运行,public static void,main(String,args,),int,weightAndPrices,=20,40,8,15,15,30,8,13,50,42,60,25;,Vector,allThings,=new Vector();,for(int,i=0;i,weightAndPrices.length;i,+),allThings.add(new,Thing(weightAndPricesi0,weightAndPricesi1);,Bag answer=solution(80,allThings,);,answer.print,();,搞忘了，待实现,public,static,void print(),System.out.println,(bag capacity:+capacity);,System.out.println,(bag,totalWeight,:+,getTotalWeight,();,System.out.println,(bag,totalValue,:+,getTotalValue,();,System.out.println,(weight t price);,for(int,i=0;i,things.size();i,+),System.out.println,(+,things.get(i).weight+tt+things.get(i).price,);,测试运行代码,Version1,。,再学习递归思想与原理,