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

《第六讲 动态规划背包问题.ppt》由会员分享，可在线阅读，更多相关《第六讲 动态规划背包问题.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、背包类动态规划问题背包类动态规划问题1经典的背包问题（经典的背包问题（01背包）背包）q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品价值件物品价值Ci元元;q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q问选取装载哪些物品，使得卡车运送的总价值问选取装载哪些物品，使得卡车运送的总价值最大？最大？2动态规划q可以按每个物品进行规划，同样每种物品有选和不选两种可以按每个物品进行规划，同样每种物品有选和不选两种选择选择q设设F(i,j)表示前表示前i件物品载重为件物品载重为j的最大效益，则有的最大效益，则有q1=i=N,0=j=wi then /背包容量够大 fi,j:=

2、max(fi-1,j-wi+ci,fi-1,j)else /背包容量不足 fi,j:=fi-1,j;end;4满背包问题（满背包问题（01背包）背包）q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品价值件物品价值Ci元元;q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q问选取装载哪些物品，使得卡车开车正好装满问选取装载哪些物品，使得卡车开车正好装满时，运送的总价值最大？时，运送的总价值最大？若无法装满卡车，则输出无解。若无法装满卡车，则输出无解。5动态规划q设设F(i,j)表示前表示前i件物品背包为件物品背包为j的最大效益，则有的最大效益，则有q1=i=N,0=j=N

3、q初值：初值：F(0,j)=0，F(1,j)=-qF(N,M)即答案即答案q显然时间复杂度为显然时间复杂度为O(NM)6带条件的背包问题（带条件的背包问题（1）q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品价值件物品价值Ci元元;q第第i件物品可能带件物品可能带02个附件；个附件；q若装载附件，必须装载主件，反之没有约束；若装载附件，必须装载主件，反之没有约束；q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q问选取装载哪些物品，使得卡车运送的总价值最大？问选取装载哪些物品，使得卡车运送的总价值最大？7分析q假设只有主件的情况假设只有主件的情况，显然与经典背包问题完全

4、相同！，显然与经典背包问题完全相同！q现在每个物品有附件，我们可以分成现在每个物品有附件，我们可以分成4种方案种方案q仅装载主件仅装载主件q装载主件装载主件+第第1个附件个附件q装载主件装载主件+第第2个附件个附件q装载主件装载主件+2个附件个附件q由于上述由于上述4种并列，这是几种不同的决策同时规划即可种并列，这是几种不同的决策同时规划即可8动态规划q设设F(i,j)表示前表示前i件物品背包为件物品背包为j的最优解，则有，的最优解，则有，q1=i=N,0=j=Mq时间复杂度时间复杂度O(NM)9多层背包问题q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品价值件物品价值C

5、i元元;q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q第第i件物品限制最多只能取件物品限制最多只能取Xi个；个；q问选取装载哪些物品，使得卡车运送的总价值最问选取装载哪些物品，使得卡车运送的总价值最大？大？10分析q我们可以类似我们可以类似01背包问题，将第背包问题，将第i种物品拆分成种物品拆分成xi个，个，这样每个物品只有这样每个物品只有1件了件了,如下图如下图:q然后对所有的物品采用动态规划即可。然后对所有的物品采用动态规划即可。qF(i,j)=max f(i-1,j-k*wi)+k*ci q0=k*wi=j11完全背包问题q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第

6、第i件物品价值件物品价值Ci元元;q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q每次可以选取某种物品的任意多件装载；每次可以选取某种物品的任意多件装载；q问选取装载哪些物品，使得卡车运送的总价值最问选取装载哪些物品，使得卡车运送的总价值最大？大？12分析q类似多层背包问题将每个物品展开成类似多层背包问题将每个物品展开成Xi=m/wi个，然个，然后对所有的物品采用动态规划即可。后对所有的物品采用动态规划即可。q若两件物品若两件物品i、j满足满足ci=wj,则将物品则将物品i去去掉掉,不用考虑。这个优化的正确性显然：任何情况下都可不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高的

7、将价值小费用高的j换成物美价廉的换成物美价廉的i,得到至少不会更差得到至少不会更差的方案。的方案。q由于每种物品有选和不选两种情况，可以将每种物品的由于每种物品有选和不选两种情况，可以将每种物品的2k个当成一个整体考虑。这样对于某种物品要选取多个，个当成一个整体考虑。这样对于某种物品要选取多个，都可以由若干个都可以由若干个2k个物品进行组合个物品进行组合(即即2进制数进制数)。例如。例如第第i种物品要选种物品要选10个，则个，则10=23+21。q这样第这样第i种物品的个数为种物品的个数为k=2(m/wi)物品，是一个很大物品，是一个很大的改进。的改进。q进一步进一步,在计算在计算k时时,K=

8、2(j/wi),j为当前背包剩余空为当前背包剩余空间。间。13进一步for i:=1 to n do /动态规划，递推求动态规划，递推求ffor j:=m downto 1 dobeginif 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改进程序q事实上，我们只关心剩

9、余背包的最大值，也就是仅仅关心事实上，我们只关心剩余背包的最大值，也就是仅仅关心f(j),因此，在对因此，在对f(j)更新时，只要背包容量可以，那么可以更新时，只要背包容量可以，那么可以反复更新。程序如下：反复更新。程序如下：for i:=1 to n do /动态规划，递推求动态规划，递推求ffor j:=0 to m dobeginif j=wi then /背包容量够大背包容量够大 fj:=max(fj-wi+ci,fj)end;15思考题思考题1：机器分配：机器分配 qM M台设备，分给台设备，分给N N个公司。个公司。q若公司若公司i i获得获得j j台设备，则能产生台设备，则能产生

10、AijAij效益效益q问问如何分配如何分配设备设备使得使得总总效益最大？效益最大？qM M=15=15，N=10N=10。16分析q用用机机器器数数来来做做状状态态，数数组组f(i,j)表表示示前前i i个个公公司司分分配配j j台机器的最大盈利。则状态转移方程为台机器的最大盈利。则状态转移方程为:qf(i,j)=Maxfi-1，k+ai，j-j(1=i=N,1=j=M,0=k=j)q初始值初始值:f(0,0)=0q时间复杂度时间复杂度O(N*M2 2)17思考题思考题2：硬币找零：硬币找零l给定给定N枚硬币枚硬币l给定给定T元钱元钱l用这用这N枚硬币找这枚硬币找这T元钱，使得剩下的钱最少。元

11、钱，使得剩下的钱最少。l剩下钱数最少的找零方案中的所需的最少硬币数。剩下钱数最少的找零方案中的所需的最少硬币数。lN=500,T=10000.18分析分析l设设Fi表示需要找的钱数为表示需要找的钱数为i时所需要的最少钱币时所需要的最少钱币数。显然有：数。显然有：lFi=MinF i-Aj +1 i T，1jNl初始值：初始值：F0=0。lAj表示其中表示其中 第第j种钱币的面值。种钱币的面值。l时间复杂度为时间复杂度为O(N*T)。19思考题思考题3：系统可靠性：系统可靠性q一一个个系系统统由由若若干干部部件件串串联联而而成成，只只要要有有一一个个部部件件故故障障，系系统统就就不不能能正正常常

12、运运行行，为为提提高高系系统统的的可可靠靠性性，每每一一部部件件都都装装有有备备用用件件，一一旦旦原原部部件件故故障障，备备用用件件就就自自动动进进入入系系统统。显显然然备备用用件件越越多多，系系统统可可靠靠性性越越高高，但但费费用用也也越越大大，那那么么在在一定总费用限制下，系统的最高可靠性等于多少？一定总费用限制下，系统的最高可靠性等于多少？q给定一些系统备用件的单价给定一些系统备用件的单价CkCk，以及当用，以及当用MkMk个此备用件时个此备用件时部件的正常工作概率部件的正常工作概率PkPk（MkMk），总费用上限），总费用上限C C。求系统可。求系统可能的最高可靠性。能的最高可靠性。2

13、0样例样例输入文件格式：输入文件格式：第一行：第一行：n Cn C第二行：第二行：C1 P1(0)P1(1)C1 P1(0)P1(1)P1(X1)P1(X1)（0=X1=C/Ck0=X1=C/Ck）第第n n 行：行：CnCn Pn(0)Pn(1)Pn(0)Pn(1)Pn(XnPn(Xn)（0=0=XnXn=C/=C/CnCn）输入：输入：2 202 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.93 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 5 0.7 0.75 0.8 0.80.8 0.9 0.95 0.9 0.95输

14、出：输出：0.63750.637521分析q设设f f(i,j(i,j)表表示示将将j j的的资资金金用用到到前前i i项项备备用用件件中中去去的的最大可靠性，则有最大可靠性，则有 F(i,jF(i,j)=)=maxF(i-1,j maxF(i-1,jk*k*CostiCosti)*)*Pi,kPi,kq 0=i=n,0=j=C,0=i=n,0=j=C,0=0=k kj div j div Cost(Cost(i i)q初始：初始：F(0,0)=0F(0,0)=0q目标：目标：F(n,CF(n,C)q时时间间复复杂杂度度：O(kO(k*n*n*C)C)，这这里里k k是是常常数数因因子子，与与

15、数数据相关据相关22思考题思考题4：快餐问题：快餐问题q套餐由由套餐由由A个汉堡，个汉堡，B个薯条和个薯条和C个饮料组成个饮料组成q生产汉堡、薯条、饮料的时间为生产汉堡、薯条、饮料的时间为p1,p2,p3q有有N条流水线，条流水线，N=10，第，第i条流水线生产时间为条流水线生产时间为Tiq每条流水线都可生产汉堡、薯条和饮料每条流水线都可生产汉堡、薯条和饮料q每天汉堡、薯条和饮料个数不超过每天汉堡、薯条和饮料个数不超过100q如何安排生产使得生产套餐数量最多。如何安排生产使得生产套餐数量最多。23分析q对于每条流水线，它的生产时间是一定的，我们对于每条流水线，它的生产时间是一定的，我们如果知道

16、了生产汉堡和薯条的个数，就很容易计如果知道了生产汉堡和薯条的个数，就很容易计算出生产饮料的个数。因此，算出生产饮料的个数。因此，q假设第假设第i条流水线生产了条流水线生产了i个汉堡，个汉堡，j个薯条个薯条,那么那么还能生产饮料个数为：还能生产饮料个数为：k=(Ti-i*p1-j*p2)/p324动态规划q设设f(x,i,j)表示前表示前x条流水线生产条流水线生产i个汉堡，个汉堡，j个薯条最多还能生产饮料个个薯条最多还能生产饮料个数。数。q如果前如果前x-1条流水线只要生产条流水线只要生产i汉堡，汉堡，j个薯条，生产的饮料为个薯条，生产的饮料为f(x-1,i,j)q因此有第因此有第x条流水线必须

17、生产了条流水线必须生产了i-i个汉堡，个汉堡，j-j个薯条，剩下的时间生个薯条，剩下的时间生产产k个饮料。个饮料。q因为前因为前x条流水线生产的饮料条流水线生产的饮料=前前x-1条流水线生产的饮料条流水线生产的饮料 +第第x条流水线生产的饮料条流水线生产的饮料q所以有，所以有，f(x,i,j)=maxf(x-1,i,j)+k25流水线资源分配图26思考？qf(x,i,j)=maxf(x-1,i,j)+k1=x=n=10,0=i=i=100,0=j=j=100qk可以实时求出可以实时求出q时间复杂度为时间复杂度为10*1002*1002=109q显然超时！显然超时！27优化1.求出最多可能生产多

18、少套，减少不必要循环。求出最多可能生产多少套，减少不必要循环。2.淘汰一些没有意义状态，比如生产了过多第三种淘汰一些没有意义状态，比如生产了过多第三种物质，却没把前两种生产满。物质，却没把前两种生产满。3.让每条流水线大多数时间按成套时间生产，留下让每条流水线大多数时间按成套时间生产，留下一些时间进行动态规划，这样将在动态规划时，一些时间进行动态规划，这样将在动态规划时，极大地减少每种物品的产量从而极大地减少动态极大地减少每种物品的产量从而极大地减少动态规划的状态数。规划的状态数。28说明q利用前两个优化基本可以出解利用前两个优化基本可以出解q第第3个优化，对每条流水线进行动态规划的剩余时间多

19、少比较难确定，个优化，对每条流水线进行动态规划的剩余时间多少比较难确定，否则正确性难以保证，剩余时间越多，正确率越高，速度越慢。下图否则正确性难以保证，剩余时间越多，正确率越高，速度越慢。下图是对第是对第3个优化的说明：个优化的说明：29总结q第第1步：采用优化方法步：采用优化方法3，将每条流水线的，将每条流水线的 部分时间按成部分时间按成套生产，设第套生产，设第i条流水线生产套餐条流水线生产套餐Wi套，剩下的时间为套，剩下的时间为Ti；q第第2步，对每条流水线的剩下时间进行动态规划步，对每条流水线的剩下时间进行动态规划,并采用优并采用优化化1，2；q第第3步，求总套数步，求总套数=贪心总套数

20、贪心总套数X+动态规划的套数动态规划的套数Y。q其中其中X,Y计算如下，计算如下，30总结总结q对于资源类动态规划问题，我们可以看出，问题描述必须有一个基本对于资源类动态规划问题，我们可以看出，问题描述必须有一个基本要素：资源，有时这种资源可能是金钱、空间或者时间，问题就是要要素：资源，有时这种资源可能是金钱、空间或者时间，问题就是要对这些资源如何分配，一种基本的想法是将资源应用于前对这些资源如何分配，一种基本的想法是将资源应用于前i个阶段，然个阶段，然后考虑第后考虑第i个阶段和前个阶段和前i-1个阶段之间的关系。个阶段之间的关系。q设前设前i个点的消耗个点的消耗j的资源得到的最优值，研究前的资源得到的最优值，研究前i-1个点消耗的资源的个点消耗的资源的最优值，利用第最优值，利用第i个点决策转移，如下图。个点决策转移，如下图。q状态转移方程一般可写成状态转移方程一般可写成:f fi i(j)=min fi-1i-1 (k)+ui(j,k)31