浅谈几类背包题课件.ppt

1、背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以0-1背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。引言背包的基本变换 完全背包 多次背包 单调队列优化其他几类背包问题 树形依赖背包（选课）PKU3093总结多次背包问题：给定多次背包问题：给定n 种物品和一个背包。第种物品和一个背包。第i种物品种物品 的价值是的价值是Wi，其体积为，其体积为Vi，数量是，数量是Ki件件，背包的容量为，背包的容量为C。可以任意选择装入背包中。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。的物品，求装入背包中物品的最大总价值。对于

2、一个左右边界都只增不降的区间最值，可以用单调队列来做到总效率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。编号编号j01234

3、对应体积dd+vd+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件物品件物品 的价值是的价值是Wi，其体积为，其体积为Vi，但是，但是依

4、赖于第依赖于第Xi件物品（必须选取件物品（必须选取Xi后才能取后才能取i，如，如果无依赖则果无依赖则Xi=0），依赖关系形成森林，背包），依赖关系形成森林，背包的容量为的容量为C。可以任意选择装入背包中的物品。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。，求装入背包中物品的最大总价值。这个概念最初是由DDengi在背包九讲中提出。定义：考虑这样一种物品，它并没有固定的费定义：考虑这样一种物品，它并没有固定的费用（体积）和价值，而是它的价值随着你分配用（体积）和价值，而是它的价值随着你分配给它的费用（体积）变化而变化。给它的费用（体积）变化而变化。泛化物品可以用一个一维数组来表示

5、体积与价值的关系Gj表示当体积为j的时候，相对应的价值为Gj(C=j=0)。显然，之前的背包动规数组Fi，就是一件泛化物品，因为Fij表示的正是体积为j的时候的最大价值。同样的，多件物品也是可以合并成一件泛化物品。泛化物品的和：泛化物品的和：把两个泛化物品合并成一个泛化物品的运算，把两个泛化物品合并成一个泛化物品的运算，就是枚举体积分配给两个泛化物品，满足：就是枚举体积分配给两个泛化物品，满足：Gj=max G1j-k+G2k (C=j=k=0)把两个泛化物品合并的时间复杂度是O(C2)。这个概念也引自背包九讲。对于这个问题，我们可以把每棵子树看作是一个泛化物品，那么一棵子树的泛化物品就是子树

6、根节点的这件物品的泛化物品与由根所连的所有子树的泛化物品的和。这就是一个O(n*C2)的算法。泛化物品与一件物品的和：泛化物品与一件物品的和：把一个泛化物品与一件物品合并成一个泛化物把一个泛化物品与一件物品合并成一个泛化物品，可以用类似于品，可以用类似于0-1背包经典动规的方法求背包经典动规的方法求出。出。泛化物品的并：泛化物品的并：因为两个泛化物品之间存在交集，所以不能同因为两个泛化物品之间存在交集，所以不能同时两者都取，那么我们就需要求泛化物品的并时两者都取，那么我们就需要求泛化物品的并，对同一体积，我们需要选取两者中价值较大，对同一体积，我们需要选取两者中价值较大的一者，效率的一者，效率

7、O(C)。考虑对以i为根的子树的处理，假设当前需要处理i的一个子节点s，体积v，价值w。如果我们在当前的Fi中强制放入物品s后作为以s为根的子树的初始状态的话，那么处理完以s为根的子树以后，Fs就是与Fi有交集的泛化物品（实际上是Fs包含Fi），同时，Fs必须满足放了物品s，即Fsj(vj=0)已经无意义了，而Fsj(C=j=v)必然包含物品s。下一步只要求Fs与Fi的并，就完成了对一个子节点的处理。对于当前节点i，我们找到一个子节点s。把Fi赋值给Fs，作为这棵子树的初始状态。递归处理以s为根的子树。编号编号012345Fia0a1a2a3a4a5编号编号012345Fsa0a1a2a3a4

8、a5si递归后就得到了最终的Fs。编号编号012345Fsb0b1b2b3b4b5siFisiFs必然包含再通过求Fi与Fs的并来完成对子节点s的更新。最后得到新的Fi，就完成了对子节点s的更新。编号编号012345Fsb0+w b1+w b2+w b3+w b4+w b5+w 编号编号vv+1v+2v+3v+4v+5Fiavav+1av+2av+3av+4av+5更新1 PROCEDURE DEAL i,C2 FOR s:=1 TO n3 IF s 是 i 的子节点 THEN4 Fi Fs5 DEAL s,C Vs /背包容量减小Vs6 FOR K:=Vs TO C /求两者的并7 Max(

9、Fi k ,Fs k-Vs +Ws)Fi k 8 END FOR9 END IF10 END FOR11 END对于每一个节点都需要更新一次，所以总效率是O(n*C+n2)。其中找子节点的可以用记边的方式来实现，总效率O(n*C)。用这个算法，可以把选课这一类treedp题优化到O(n*C)，亦可以作为noip06金明的预算方案的O(n*C)treedp解法。由背包转变出的题有很多，其中不乏难题，今天给大家介绍了两种最常见的变形，最后都以O(n*C)的算法解决了。就目前来说，背包类的题目还有很多没有得到很好的解决，等待着大家去继续探索研究。特别感谢白彦博金圣玺冯一参考资料Ddengi的背包九讲