算法合集之《浅谈几类背包题》.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,徐持衡,浙江省温州中学,背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以,0-1,背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。,引言,背包的基本变换,完全背包,多次背包,单调队列优化,其他几类背包问题,树形依赖背包（选课）,PKU3093,总结,多次背包问题：给定,n,种物品和一个背包。第,i,种物品 的价值是,W,i,，其体积为,V,i,，数量是,K,i,件，背包的容量为,C,。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。,对于一个左右边界都只增不降的区间最值，可以用单调队列来做到总效率,O(n),的维护。,如果要用单调队列来优化多次背包，就必须在多次背包问题中挖掘出一个维护区间最值的子问题。,对于多次背包，用最常见的状态表示是用,Fi,j,表示前,i,种物品，总体积不超过,j,的最大价值总和。,当前只考虑第,i,种物品，假设体积,v,，价值,w,，数量,k,。,由于对于体积,j,，与其相关的只有那些对,v,的余数与,j,相同的体积，所以再按照体积,j,对,v,的余数分为,v,份。,我们可以把每一份分开处理，假设现在要考虑余数为,d,的部分。,用,j,来标号，规定编号,j,所对应的体积是,d+j*v,。,显然编号,j,可以从编号,j-k,到,j,中的任意一个转移而来，因为相邻的体积正好相差,v,。,编号,j,0,1,2,3,4,对应体积,d,d+v,d+2*v,d+3*v,d+4*v,区间,j-k,j,，这个区间是随着,j,的递增而左右边界都递增的区间。,但是注意到由于不同编号对应的体积也是不一样的，显然体积大的价值也会大于等于体积小的，直接比较是没有意义的，所以还需要做一定的修正。,比如可以把体积,d+j*v,都退化到,d,，也就是说用,Fi-1,j*v+d-j*w,来代替原来的价值进行比较大小。,这样就可以用单调队列来优化了，对于每件物品的转移均摊,O(C),，所以得到,O(n*C),的算法。,树形依赖背包问题：给定,n,件物品和一个背包。第,i,件物品 的价值是,W,i,，其体积为,V,i,，但是依赖于第,X,i,件物品（必须选取,X,i,后才能取,i,，如果无依赖则,X,i,=0,），依赖关系形成森林，背包的容量为,C,。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。,这个概念最初是由,DDengi,在,背包九讲,中提出。,定义：考虑这样一种物品，它并没有固定的费用（体积）和价值，而是它的价值随着你分配给它的费用（体积）变化而变化。,泛化物品可以用一个一维数组来表示体积与价值的关系,Gj,表示当体积为,j,的时候，相对应的价值为,Gj(C=j=0),。,显然，之前的背包动规数组,F,i,，就是一件泛化物品，因为,F,i,j,表示的正是体积为,j,的时候的最大价值。同样的，多件物品也是可以合并成一件泛化物品。,泛化物品的和：,把两个泛化物品合并成一个泛化物品的运算，就是枚举体积分配给两个泛化物品，满足：,Gj=max G,1,j-k+G,2,k (C=j=k=0),把两个泛化物品合并的时间复杂度是,O(C2),。,这个概念也引自,背包九讲,。,对于这个问题，我们可以把每棵子树看作是一个泛化物品，那么一棵子树的泛化物品就是子树根节点的这件物品的泛化物品与由根所连的所有子树的泛化物品的和。,这就是一个,O(n*C2),的算法。,泛化物品与一件物品的和：,把一个泛化物品与一件物品合并成一个泛化物品，可以用类似于,0-1,背包经典动规的方法求出。,泛化物品的并：,因为两个泛化物品之间存在交集，所以不能同时两者都取，那么我们就需要求泛化物品的并，对同一体积，我们需要选取两者中价值较大的一者，效率,O(C),。,考虑对以,i,为根的子树的处理，假设当前需要处理,i,的一个子节点,s,，体积,v,，价值,w,。,如果我们在当前的,F,i,中强制放入物品,s,后作为以,s,为根的子树的初始状态的话，那么处理完以,s,为根的子树以后，,F,s,就是与,F,i,有交集的泛化物品（实际上是,F,s,包含,F,i,），同时，,F,s,必须满足放了物品,s,，即,F,s,j(vj=0),已经无意义了，而,F,s,j(C=j=v),必然包含物品,s,。,下一步只要求,F,s,与,F,i,的并，就完成了对一个子节点的处理。,对于当前节点,i,，我们找到一个子节点,s,。,把,F,i,赋值给,F,s,，作为这棵子树的初始状态。,递归处理以,s,为根的子树。,编号,0,1,2,3,4,5,F,i,a,0,a,1,a,2,a,3,a,4,a,5,编号,0,1,2,3,4,5,F,s,a,0,a,1,a,2,a,3,a,4,a,5,s,i,递归后就得到了最终的,F,s,。,编号,0,1,2,3,4,5,F,s,b,0,b,1,b,2,b,3,b,4,b,5,s,i,F,i,s,i,F,s,必然包含,再通过求,F,i,与,F,s,的并来完成对子节点,s,的更新。,最后得到新的,F,i,，就完成了对子节点,s,的更新。,编号,0,1,2,3,4,5,F,s,b,0,+w,b,1,+w,b,2,+w,b,3,+w,b,4,+w,b,5,+w,编号,v,v+1,v+2,v+3,v+4,v+5,F,i,a,v,a,v+1,a,v+2,a,v+3,a,v+4,a,v+5,更新,1,PROCEDURE DEAL i,C,2 FOR s:=1 TO n,3 IF s,是,i,的子节点,THEN,4 F,i,F,s,5 DEAL s,C V,s,/,背包容量减小,V,s,6 FOR K:=V,s,TO C /,求两者的并,7 Max(F,i,k ,F,s,k-V,s,+W,s,),F,i,k,8 END FOR,9 END IF,10 END FOR,11 END,对于每一个节点都需要更新一次，所以总效率是,O(n*C+n2),。,其中找子节点的可以用记边的方式来实现，总效率,O(n*C),。,用这个算法，可以把,选课,这一类,treedp,题优化到,O(n*C),，亦可以作为,noip06,金明的预算方案,的,O(n*C)treedp,解法。,由背包转变出的题有很多，其中不乏难题，今天给大家介绍了两种最常见的变形，最后都以,O(n*C),的算法解决了。,就目前来说，背包类的题目还有很多没有得到很好的解决，等待着大家去继续探索研究。,特别感谢,白彦博,金圣玺,冯一,参考资料,Ddengi,的,背包九讲,徐持衡,浙江省温州中学,