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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,背包类动态规划问题,1,经典的背包问题（,01,背包）,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,问选取装载哪些物品，使得卡车运送的总价值最大？,2,动态规划,可以按每个物品进行规划，同样每种物品有选和不选两种选择,设,F(i,j,),表示前,i,件物品载重为,j,的最大效益，则有,1=i=N,0=j=,wi,then /,背包容量够大,fi,j,:=max(fi-1,j-wi+ci,fi-1,j),else /,背包容量不足,fi,j,:=fi-1,j;,end;,4,满背包问题（,01,背包）,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,问选取装载哪些物品，使得卡车开车正好装满时，运送的总价值最大？,若无法装满卡车，则输出无解。,5,动态规划,设,F(i,j,),表示前,i,件物品背包为,j,的最大效益，则有,1=i=N,0=j=N,初值：,F(0,j)=0,，,F(1,j)=-,F(N,M),即答案,显然时间复杂度为,O(NM),6,带条件的背包问题（,1,）,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,第,i,件物品可能带,02,个附件；,若装载附件，必须装载主件，反之没有约束；,现有一辆载重,M,公斤的卡车,;,问选取装载哪些物品，使得卡车运送的总价值最大？,7,分析,假设只有主件的情况，显然与经典背包问题完全相同！,现在每个物品有附件，我们可以分成,4,种方案,仅装载主件,装载主件,+,第,1,个附件,装载主件,+,第,2,个附件,装载主件,+2,个附件,由于上述,4,种并列，这是几种不同的决策同时规划即可,8,动态规划,设,F(i,j,),表示前,i,件物品背包为,j,的最优解，则有，,1=i=N,0=j=M,时间复杂度,O(NM),9,多层背包问题,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,第,i,件物品限制最多只能取,Xi,个；,问选取装载哪些物品，使得卡车运送的总价值最大？,10,分析,我们可以类似,01,背包问题，将第,i,种物品拆分成,xi,个，这样每个物品只有,1,件了,如下图,:,然后对所有的物品采用动态规划即可。,F(i,j,)=max f(i-1,j-k*,wi,)+k*,ci,0=k*,wi,=j,11,完全背包问题,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,每次可以选取某种物品的任意多件装载；,问选取装载哪些物品，使得卡车运送的总价值最大？,12,分析,类似多层背包问题将每个物品展开成,Xi,=,m/wi,个，然后对所有的物品采用动态规划即可。,若两件物品,i,、,j,满足,ci,=,wj,则将物品,i,去掉,不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的,j,换成物美价廉的,i,得到至少不会更差的方案。,由于每种物品有选和不选两种情况，可以将每种物品的,2,k,个当成一个整体考虑。这样对于某种物品要选取多个，都可以由若干个,2,k,个物品进行组合,(,即,2,进制数,),。例如第,i,种物品要选,10,个，则,10=2,3,+2,1,。,这样第,i,种物品的个数为,k=,2,(,m/w,i,),物品，是一个很大的改进。,进一步,在计算,k,时,K=,2,(,j/w,i,),j,为当前背包剩余空间。,13,进一步,for i:=1 to n do /,动态规划，递推求,f,for j:=m,downto,1 do,begin,if j=,wi,then /,背包容量够大,fi,j,:=max(fi-1,j-wi+ci,fi-1,j),else /,背包容量不足,fi,j,:=fi-1,j;,end;,在这里为了使得每个物品只取,1,个或不取,采用了每次取,j,都是与,i-1,进行比较，实际上保存了每,1,步取不同,j,的值,14,改进程序,事实上，我们只关心剩余背包的最大值，也就是仅仅关心,f(j,),因此，在对,f(j,),更新时，只要背包容量可以，那么可以反复更新。程序如下：,for i:=1 to n do /,动态规划，递推求,f,for j:=0 to m do,begin,if j=,wi,then /,背包容量够大,fj,:=,max(fj-wi+ci,fj,),end;,15,思考题,1,：机器分配,M,台设备，分给,N,个公司。,若公司,i,获得,j,台设备，则能产生,Aij,效益,问如何分配设备使得总效益最大？,M,=15,，,N=10,。,16,分析,用机器数来做状态，数组,f(i,j,),表示前,i,个公司分配,j,台机器的最大盈利。则状态转移方程为,:,f(i,j,)=Maxfi-1,，,k+,ai,，,j-j,(1=i=N,1=j=M,0,=k=j),初始值,:f(0,0)=0,时间复杂度,O(N*M,2,),17,思考题,2,：硬币找零,给定,N,枚硬币,给定,T,元钱,用这,N,枚硬币找这,T,元钱，使得剩下的钱最少。,剩下钱数最少的找零方案中的所需的最少硬币数。,N=500,T=10000.,18,分析,设,Fi,表示需要找的钱数为,i,时所需要的最少钱币数。显然有：,Fi,=,MinF,i-,Aj,+1 i,T,，,1,j,N,初始值：,F0=0,。,Aj,表示其中,第,j,种钱币的面值。,时间复杂度为,O(N*T),。,19,思考题,3,：系统可靠性,一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？,给定一些系统备用件的单价,Ck,，以及当用,Mk,个此备用件时部件的正常工作概率,Pk,（,Mk,），总费用上限,C,。求系统可能的最高可靠性。,20,样例,输入文件格式：,第一行：,n C,第二行：,C1 P1(0)P1(1),P1(X1),（,0=X1=C/Ck,）,第,n,行：,Cn,Pn(0)Pn(1),Pn(Xn,),（,0=,Xn,=C/,Cn,）,输入：,2 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.9,5 0.7 0.75 0.8,0.8,0.9 0.95,输出：,0.6375,21,分析,设,f,(i,j,),表示将,j,的资金用到前,i,项备用件中去的最大可靠性，则有,F(i,j,)=,maxF(i-1,j,k*,Costi,)*,Pi,k,0=i=n,0=j=C,0=,k,j div,Cost(,i,),初始：,F(0,0)=0,目标：,F(n,C,),时间复杂度：,O(k,*n,*,C),，这里,k,是常数因子，与数据相关,22,思考题,4,：快餐问题,套餐由由,A,个汉堡，,B,个薯条和,C,个饮料组成,生产汉堡、薯条、饮料的时间为,p1,p2,p3,有,N,条流水线，,N=10,，第,i,条流水线生产时间为,Ti,每条流水线都可生产汉堡、薯条和饮料,每天汉堡、薯条和饮料个数不超过,100,如何安排生产使得生产套餐数量最多。,23,分析,对于每条流水线，它的生产时间是一定的，我们如果知道了生产汉堡和薯条的个数，就很容易计算出生产饮料的个数。因此，,假设第,i,条流水线生产了,i,个汉堡，,j,个薯条,那么还能生产饮料个数为：,k=(Ti-i*p1-j*p2)/p3,24,动态规划,设,f(x,i,j,),表示前,x,条流水线生产,i,个汉堡，,j,个薯条最多还能生产饮料个数。,如果前,x-1,条流水线只要生产,i,汉堡，,j,个薯条，生产的饮料为,f(x-1,i,j),因此有第,x,条流水线必须生产了,i-i,个汉堡，,j-j,个薯条，剩下的时间生产,k,个饮料。,因为前,x,条流水线生产的饮料,=,前,x-1,条流水线生产的饮料,+,第,x,条流水线生产的饮料,所以有，,f(x,i,j,)=maxf(x-1,i,j)+k,25,流水线资源分配图,26,思考？,f(x,i,j,)=maxf(x-1,i,j)+k,1=x=n=10,0=i=i=100,0=j=j=100,k,可以实时求出,时间复杂度为,10*100,2,*,100,2,=10,9,显然超时！,27,优化,求出最多可能生产多少套，减少不必要循环。,淘汰一些没有意义状态，比如生产了过多第三种物质，却没把前两种生产满。,让每条流水线大多数时间按成套时间生产，留下一些时间进行动态规划，这样将在动态规划时，极大地减少每种物品的产量从而极大地减少动态规划的状态数。,28,说明,利用前两个优化基本可以出解,第,3,个优化，对每条流水线进行动态规划的剩余时间多少比较难确定，否则正确性难以保证，剩余时间越多，正确率越高，速度越慢。下图是对第,3,个优化的说明：,29,总结,第,1,步：采用优化方法,3,，将每条流水线的,部分时间按成套生产，设第,i,条流水线生产套餐,Wi,套，剩下的时间为,Ti,；,第,2,步，对每条流水线的剩下时间进行动态规划,并采用优化,1,，,2,；,第,3,步，求总套数,=,贪心总套数,X,+,动态规划的套数,Y,。,其中,X,Y,计算如下，,30,总结,对于资源类动态规划问题，我们可以看出，问题描述必须有一个基本要素：资源，有时这种资源可能是金钱、空间或者时间，问题就是要对这些资源如何分配，一种基本的想法是将资源应用于前,i,个阶段，然后考虑第,i,个阶段和前,i-1,个阶段之间的关系。,设前,i,个点的消耗,j,的资源得到的最优值，研究前,i-1,个点消耗的资源的最优值，利用第,i,个点决策转移，如下图。,状态转移方程一般可写成,:,f,i,(j,)=min f,i-1,(k)+,u,i,(,j,k,),31,