资源背包动态规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,背包类动态规划问题,经典的背包问题（,01,背包）,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,问选取装载哪些物品，使得卡车运送的总价值最大？,搜索法,对于每种物品，要么装上卡车，要么不装，因此，,N,种物品的装箱方案共有,2,N,种。,按每种物品进行搜索，方法如下：,对第,i,种物品进行搜索,如果所有的物品都搜索完，则更新最优解,如果当前的估计达不到最优解，则回溯,如果第,i,种物品能放，则放，并标记，否则选下一个物品,清除标记,回溯,动态规划,可以按每个物品进行规划，同样每种物品有选和不选两种选择,设,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;,满背包问题（,01,背包）,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,问选取装载哪些物品，使得卡车开车正好装满时，运送的总价值最大？,若无法装满卡车，则输出无解。,动态规划,设,F(i,j),表示前,i,件物品背包为,j,的最大效益，则有,1=i=N,0=j=N,初值：,F(0,j)=0,，,F(1,j)=,-,F(N,M),即答案,显然时间复杂度为,O(NM),带条件的背包问题（,1,）,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,第,i,件物品可能带,02,个附件；,若装载附件，必须装载主件，反之没有约束；,现有一辆载重,M,公斤的卡车,;,问选取装载哪些物品，使得卡车运送的总价值最大？,分析,假设只有主件的情况，显然与经典背包问题完全相同！,现在每个物品有附件，我们可以分成,4,种方案,仅装载主件,装载主件,+,第,1,个附件,装载主件,+,第,2,个附件,装载主件,+2,个附件,由于上述,4,种并列，这是几种不同的决策同时规划即可,动态规划,设,F(i,j),表示前,i,件物品背包为,j,的最优解，则有，,1=i=N,0=j=M,时间复杂度,O(NM),多层背包问题,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,第,i,件物品限制最多只能取,Xi,个；,问选取装载哪些物品，使得卡车运送的总价值最大？,分析,我们可以类似,01,背包问题，将第,i,种物品拆分成,xi,个，这样每个物品只有,1,件了,如下图,:,然后对所有的物品采用动态规划即可。,F(i,j)=max f(i-1,j-k*wi)+k*ci,0=k*wi=j,完全背包问题,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,每次可以选取某种物品的任意多件装载；,问选取装载哪些物品，使得卡车运送的总价值最大？,分析,类似多层背包问题将每个物品展开成,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,为当前背包剩余空间。,进一步,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,的值,改进程序,事实上，我们只关心剩余背包的最大值，也就是仅仅关心,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;,思考题,1,：机器分配,M,台设备，分给,N,个公司。,若公司,i,获得,j,台设备，则能产生,Aij,效益,问如何分配设备使得总效益最大？,M,=15,，,N=10,。,分析,用机器数来做状态，数组,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,),思考题,2,：硬币找零,给定,N,枚硬币,给定,T,元钱,用这,N,枚硬币找这,T,元钱，使得剩下的钱最少。,剩下钱数最少的找零方案中的所需的最少硬币数。,N=500,T=10000.,分析,设,Fi,表示需要找的钱数为,i,时所需要的最少钱币数。显然有：,Fi=MinF i-Aj +1 i,T,，,1,j,N,初始值：,F0=0,。,Aj,表示其中,第,j,种钱币的面值。,时间复杂度为,O(N*T),。,思考题,3,：系统可靠性,一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？,给定一些系统备用件的单价,Ck,，以及当用,Mk,个此备用件时部件的正常工作概率,Pk,（,Mk,），总费用上限,C,。求系统可能的最高可靠性。,样例,输入文件格式：,第一行：,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,分析,设,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,是常数因子，与数据相关,思考题,4,：快餐问题,套餐由由,A,个汉堡，,B,个薯条和,C,个饮料组成,生产汉堡、薯条、饮料的时间为,p1,p2,p3,有,N,条流水线，,N=10,，第,i,条流水线生产时间为,Ti,每条流水线都可生产汉堡、薯条和饮料,每天汉堡、薯条和饮料个数不超过,100,如何安排生产使得生产套餐数量最多。,分析,对于每条流水线，它的生产时间是一定的，我们如果知道了生产汉堡和薯条的个数，就很容易计算出生产饮料的个数。因此，,假设第,i,条流水线生产了,i,个汉堡，,j,个薯条,那么还能生产饮料个数为：,k=(Ti-i*p1-j*p2)/p3,动态规划,设,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,流水线资源分配图,思考？,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,显然超时！,优化,求出最多可能生产多少套，减少不必要循环。,淘汰一些没有意义状态，比如生产了过多第三种物质，却没把前两种生产满。,让每条流水线大多数时间按成套时间生产，留下一些时间进行动态规划，这样将在动态规划时，极大地减少每种物品的产量从而极大地减少动态规划的状态数。,说明,利用前两个优化基本可以出解,第,3,个优化，对每条流水线进行动态规划的剩余时间多少比较难确定，否则正确性难以保证，剩余时间越多，正确率越高，速度越慢。下图是对第,3,个优化的说明：,总结,第,1,步：采用优化方法,3,，将每条流水线的,部分时间按成套生产，设第,i,条流水线生产套餐,Wi,套，剩下的时间为,Ti,；,第,2,步，对每条流水线的剩下时间进行动态规划,并采用优化,1,，,2,；,第,3,步，求总套数,=,贪心总套数,X,+,动态规划的套数,Y,。,其中,X,Y,计算如下，,总结,对于资源类动态规划问题，我们可以看出，问题描述必须有一个基本要素：资源，有时这种资源可能是金钱、空间或者时间，问题就是要对这些资源如何分配，一种基本的想法是将资源应用于前,i,个阶段，然后考虑第,i,个阶段和前,i-1,个阶段之间的关系。,设前,i,个点的消耗,j,的资源得到的最优值，研究前,i-1,个点消耗的资源的最优值，利用第,i,个点决策转移，如下图。,状态转移方程一般可写成,:,f,i,(j)=min f,i-1,(k)+u,i,(j,k),