第六讲 动态规划背包问题详细.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,背包问题的,探究,一.01背包,题目：,有,N件物品,和一个,容量为V,的背包。第i件物品的费用是ci，价值是wi。求解将哪些物品装入背包可使,价值总和最大。,基本思路：,这是,最基础的背包问题,，特点是：每种物品仅有一件，可以选择放或不放,先列方程再解释：,用子问题定义状态：即fiv表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其,状态转移方程,便是：,fiv=maxfi-1v,fi-1v-ci+wi,这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的,一.01背包,解释：,“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以,转化,为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为fi-1v；如果放第i件物品，那么问题就,转化,为“前i-1件物品放入剩下的容量为v-ci的背包中”，此时能获得的最大价值就是fi-1v-ci再加上通过放入第i件物品获得的价值wi。,一.01背包,注意：转化过程！,伪码：,for i=1.N,for v=0.V,fv=maxfv,fv-ci+wi;,一.01背包,时间复杂度：O(VN).,空间复杂度：O(VN).,优化：空间复杂度可以优化！时间复杂度也可以进行常数优化.,应该是for v=V.0,二.完全背包,题目:,有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。,简单优化：,1）若两件物品i、j满足ci=wj，则将物品j去掉，不用考虑.,2）将费用大于V的物品去掉.,转化为01背包：,考虑到第i种物品最多选V/ci件，于是可以把第i种物品转化为V/ci件费用及价值均不变的物品，然后求解这个01背包问题,二.完全背包,还可以优化的更高效！,二进制思想,伪码：,for i=1.N,for v=0.V,fv=maxfv,fv-cost+weight,注意：,此处,v的循环次序,和01背包的,循环次序不同,！,假如合理的交换v，n的循环次序，貌似可以稍稍的提高效率.,二.完全背包,此处仍然可以用,一维数组存储,二.完全背包,下面分析为何伪码可以成立。最原始的代码应该是：,for i=1.N,for v=0.V,fiv=maxfi-1v-k*ci+k*wi|0=kni)break;/,zopackcnt+=2k;,sum+=2k;,zopackcnt+=ni-sum;/,这里对于每一个ni都有一个zopack;然后将每一zopack看作01背包的每一个物品就可以按照01背包的思想做了。,三.多重背包,四混合三种背包问题,题目：,将二，三，四三种背包问题混合起来。,有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？，,伪码：,for i=1.N,if 第i件物品属于01背包 ZeroOnePack(ci,wi),else if 第i件物品属于完全背包 CompletePack(ci,wi),else if 第i件物品属于多重背包 MultiplePack(ci,wi,ni),四.混合三种背包问题,题目:,二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为ai和bi。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为wi。,五.,二维费用的背包问题,算法：,费用加了一维，只需状态也加一维即可。设fivu表示前i件物品付出两种代价分别为v和u时可获得的最大价值。,状态转移方程就是：,fivu=maxfi-1vu,fi-1v-aiu-bi+wi,五.,二维费用的背包问题,注：,可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用,逆序的循环,，当物品有如完全背包问题时采用,顺序的循环,。当物品有如多重背包问题时,拆分物品,。,五.,二维费用的背包问题,六.分组的背包问题,题目：,有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。,算法：,这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设,fkv,表示前,k,组物品花费费用,v,能取得的最大权值,状态方程：,fkv,=maxfk-1v,fk-1v-ci+wi|,物品,i,属于组,k,六.分组的背包问题,伪码：,for 所有的组k,for v=V.0,for 所有的i属于组k,fv=maxfv,fv-ci+wi,六.分组的背包问题,注意：,“,for v=V.0,”,这一层循环必须在,“,for 所有的i属于组k,”,之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。,仍然可以对每组中做像,完全背包那样的优化,伪码中第三层循环思想上有所跳跃，可以这样理解。先考虑正在处理的这组(k)中只有一种物品，那么这层循环就没必要了（仅对这一组来说），如果只有两种物品呢？我们也可以分别考虑它们的取与不取从而得到最大值。如果是三种呢（a,b,c)？那么代码可能是这样子的(我把它写成二维的)：,max1=maxfk-1v,fk-1v-ca+wa,max2=maxfk-1v,fk-1v-cb+wb,max3=maxfk-1v,fk-1v-cc+wc,fkv=maxmax1,max2,max3,六.分组的背包问题,在求得max1之后我们就可以说fkv的最大值不会小于max1,我们将它的底限提高到了max1（max1也有可能等于fk-1v，但不会小于它）。于是我们可以放心地把第二句改为：,max2=maxmax1,fk-1v-cb+wb,当然这时max2原先的意思就没有了，它只是求fkv的一个中间变量，第三句也可变成,Max3=maxmax2,fk-1v-cc+wc,其实这时max3就是所要求的fkv了，我们完全没有必要浪费maxi这三个变量的空间。于是代码又成为：,六.分组的背包问题,Fkv=maxfk-1v,fk-1v-ca+wa,Fkv=maxfkv,fk-1v-cb+wb,Fkv=maxfkv,fk-1v-cc+wc,写回一维的形式即:,Fv=maxfv,fvv-ca+wa,Fv=maxfv,fvv-cb+wb,Fv=maxfv,fvv-cc+wc,这样太麻烦了，写成循环的形式吧，于是便成了前面伪码的模样。,六.分组的背包问题,从前面的分析我们知道在伪码中只有第一次循时max.里面的那个fv,才是fk-1v;只有最后一次循环时max.外面的那个fv才是fkv,其它的都是中间的变量，并没有什么实际的意义。,六.分组的背包问题,七.有依赖的背包问题,题目：,这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品,分析：,可以对每组中的物品应用,完全背包,中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，,我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0.V-ci所有这些值时相应的最大价值f0.V-ci。那么这个主件及它的附件集合相当于V-ci+1个物品的物品组，其中费用为ci+k的物品的价值为fk+wi,。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为V-ci+1个物品的物品组，就可以直接应用,分组背包,的算法解决问题了,七.有依赖的背包问题,这一点是为什么呢？,八.泛化物品,定义,：考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0.V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)。,八.泛化物品,其,他物品向泛化物品的转化,：一个费用为,c,价值为,w,的物品，如果它是,01,背包中的物品，那么把它看成泛化物品，它就是除了,h(c)=w,其它函数值都为,0,的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当,v,被,c,整除时有,h(v)=v/c*w,，其它函数值均为,0,。如果它是多重背包中重复次数最多为,n,的物品，那 么它对应的泛化物品的函数有,h(v)=v/c*w,仅当,v,被,c,整除且,v/c=n,，其它情况函数值均为,0,。一个物品组可以看作一个泛化物品,h,。对于一个,0.V,中的,v,，若物品组中不存在费用为,v,的的物品，则,h(v)=0,，否则,h(v),为所有费用为,v,的物品的最大价值。,八.泛化物品,泛化物品的和,：如果面对两个泛化物品h和l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0.V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)。也即,f(v)=maxh(k)+l(v-k)|0=kmin),输出方案：用时是要输出最佳方案的，由于背包问题是动态归化问题，可以用动态归化中记录每个状态转移并逆序求解的方法来解决。,九.背包问题问法的变化,要,求背包装满,：这时在求解每个状态（状态,1,）的最大价值时要对转移到它的状态（状态,2,）是否是完全装满的作讨论。如果状态,2,没有装满，我们是不能考虑它的，因为它会导致状态,1,也没装满，这种影响一直传递下去。到求得,fNV,时可能也是末装满的。而我们也没必要每次都讨论，我们可以把,fiv,的定义改下：将前,i,个物品装入容量为,v,的背包中恰好装满的最大价值量。如果我们发现,fiv=0,说明前,i,个物品不能将它恰好装满。但对于,fi0,，它肯定是等于,0,的，但我们要把它作装满看待。因为容量为,0,的背包装了花费,0,是装满了的，要不然你还想怎么着。,九.背包问题问法的变化,求方案总数,：将,fiv,定义为将用前,i,个物品将容量为,v,的背包装满的方案总数，可用一种从前往后类似动态归化的递推的方法，也可以简单地将前面背包中的,max,改为,sum,状态转移方程为：,fiv,=sumfi-1v,fiv-ci,