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

1、背包类动态规划问题背包类动态规划问题经典的背包问题经典的背包问题01背包背包q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品价值件物品价值Ci元元;q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q问选取装载哪些物品，使得卡车运送的总价值问选取装载哪些物品，使得卡车运送的总价值最大？最大？动态规划q 可以按每个物品进展规划，同样每种物品有选和不选两种可以按每个物品进展规划，同样每种物品有选和不选两种选择选择q 设设F(i,j)表示前表示前i件物品载重为件物品载重为j的最大效益，那么有的最大效益，那么有q 1=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;满背包问题满背包问题01背包背包q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品价值件物品价值Ci元元;q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q问选取装载哪些物品，使得卡车开车正好装满问选取装载哪些物品，使得卡车开车正好装满时，运送的总价值最大？时，运送的总价值最大？q假设无法装满卡车，那么输出无解。假设无法装满卡车，那么输出无解。动态规划q设设F(i,j)表示前表示前i件物品背包为件物品背包为j的最大效益，那么的最大效益，那么有有q1=i=N, 0=j

3、=Nq初值：初值：F(0,j)=0， F(1,j)= -qF(N,M)即答案即答案q显然时间复杂度为显然时间复杂度为O(NM)种物品不装载第种物品装载第ijiFiiCiwjiFMaxjiF), 1(,), 1(),(带条件的背包问题带条件的背包问题1q 有有N件物品件物品;q 第第i件物品件物品Wi公斤公斤;q 第第i件物品价值件物品价值Ci元元;q 第第i件物品能够带件物品能够带02个附件；个附件；q 假设装载附件，必需装载主件，反之没有约束；假设装载附件，必需装载主件，反之没有约束；q 现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q 问选取装载哪些物品，使得卡车运送的总价值最大？问选取

4、装载哪些物品，使得卡车运送的总价值最大？分析q 假设只需主件的情况假设只需主件的情况 ，显然与经典背包问题完全一样！，显然与经典背包问题完全一样！q 如今每个物品有附件，我们可以分成如今每个物品有附件，我们可以分成4种方案种方案q 仅装载主件仅装载主件q 装载主件装载主件+第第1个附件个附件q 装载主件装载主件+第第2个附件个附件q 装载主件装载主件+2个附件个附件q 由于上述由于上述4种并列，这是几种不同的决策同时规划即可种并列，这是几种不同的决策同时规划即可动态规划q 设设F(i,j)表示前表示前i件物品背包为件物品背包为j的最优解，那么有，的最优解，那么有，q 1=i=N, 0=j=Mq

5、 时间复杂度时间复杂度O(NM)件附件选主件和，件附件选主件和第，件附件选主件和第，只选主件件物品不选第2/21)2-1w-, 1(2/2)2-, 1(1/1)1w-, 1(), 1(i), 1(),(iciciciwiiwjiFiciciwiwjiFiciciiwjiFiciwjiFjiFMaxjiF多层背包问题q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品价值件物品价值Ci元元;q现有一辆载重现有一辆载重M公斤的卡车公斤的卡车;q第第i件物品限制最多只能取件物品限制最多只能取Xi个；个；q问选取装载哪些物品，使得卡车运送的总价值最问选取装载哪些物品，使得卡车运送的总

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

7、送的总价值最问选取装载哪些物品，使得卡车运送的总价值最大？大？分析q 类似多层背包问题将每个物品展开成类似多层背包问题将每个物品展开成Xi =m/wi个，然个，然后对一切的物品采用动态规划即可。后对一切的物品采用动态规划即可。q 假设两件物品假设两件物品i、j满足满足ci=wj,那么将物那么将物品品i去掉去掉,不用思索。这个优化的正确性显然：任何情况不用思索。这个优化的正确性显然：任何情况下都可将价值小费用高的下都可将价值小费用高的j换成物美价廉的换成物美价廉的i,得到至少不得到至少不会更差的方案。会更差的方案。q 由于每种物品有选和不选两种情况，可以将每种物品的由于每种物品有选和不选两种情况

8、，可以将每种物品的2k个当成一个整体思索。这样对于某种物品要选取多个，个当成一个整体思索。这样对于某种物品要选取多个，都可以由假设干个都可以由假设干个2k个物品进展组合个物品进展组合 (即即2进制数进制数)。例。例如第如第i种物品要选种物品要选10个，那么个，那么10=23+21 。q 这样第这样第i种物品的个数为种物品的个数为k=2 (m/wi)物品，是一个很大物品，是一个很大的改良。的改良。q 进一步进一步, 在计算在计算k时时, K =2 (j/wi), j为当前背包剩余空间。为当前背包剩余空间。进一步for i:=1 to n do / 动态规划，递推求动态规划，递推求ffor j:=

9、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的值的值改良程序q 现实上，我们只关怀剩余背包的最大值，也就是仅仅关怀现实上，我们只关怀剩余背包的最大值，也就是仅仅关怀f(j),因此，在对因此，在对f(j)更新时，只需背包容量可以，那么可以

10、更新时，只需背包容量可以，那么可以反复更新。程序如下：反复更新。程序如下：qfor i:=1 to n do / 动态规划，递推求动态规划，递推求fqfor j:=0 to m doqbeginqif j=wi then /背包容量够大背包容量够大q fj:=max(fj-wi+ci,fj)qend;思索题思索题1：机器分配：机器分配 qM M台设备，分给台设备，分给N N个公司。个公司。q假设公司假设公司i i获得获得j j台设备，那么能产生台设备，那么能产生AijAij效益效益q问如何分配设备使得总效益最大？问如何分配设备使得总效益最大？qM=15M=15，N=10N=10。分析q用机器数

11、来做形状，数组用机器数来做形状，数组f(i,j)f(i,j)表示前表示前i i个公司分个公司分配配j j台机器的最大盈利。那么形状转移方程为台机器的最大盈利。那么形状转移方程为: :qf(i,j) =Maxfi-1f(i,j) =Maxfi-1，k + aik + ai，j-j j-j (1=i=N,1=j=M,0=k=j )(1=i=N,1=j=M,0=k=j )q初始值初始值: f(0,0)=0: f(0,0)=0q时间复杂度时间复杂度O(NO(N* *M2)M2)思索题思索题2：硬币找零：硬币找零l 给定给定N枚硬币枚硬币l 给定给定T元钱元钱l 用这用这N枚硬币找这枚硬币找这T元钱，使

12、得剩下的钱最少。元钱，使得剩下的钱最少。l 剩下钱数最少的找零方案中的所需的最少硬币数。剩下钱数最少的找零方案中的所需的最少硬币数。l N=500,T=10000.分析分析l 设设Fi表示需求找的钱数为表示需求找的钱数为i时所需求的最少钱币时所需求的最少钱币数。显然有：数。显然有：l Fi=MinF i - Aj + 1 i T，1jNl 初始值：初始值：F0=0。l Aj表示其中表示其中 第第j种钱币的面值。种钱币的面值。l 时间复杂度为时间复杂度为O(N*T)。思索题思索题3：系统可靠性：系统可靠性q 一个系统由假设干部件串联而成，只需有一个部件缺点，一个系统由假设干部件串联而成，只需有一

13、个部件缺点，系统就不能正常运转，为提高系统的可靠性，每一部件系统就不能正常运转，为提高系统的可靠性，每一部件都装有备用件，一旦原部件缺点，备用件就自动进入系都装有备用件，一旦原部件缺点，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？那么在一定总费用限制下，系统的最高可靠性等于多少？q 给定一些系统备用件的单价给定一些系统备用件的单价CkCk，以及当用，以及当用MkMk个此备用件个此备用件时部件的正常任务概率时部件的正常任务概率PkPkMkMk，总费用上限，总费用上限C C。

14、求系统。求系统能够的最高可靠性。能够的最高可靠性。 样例样例输入文件格式：输入文件格式：第一行：第一行：n Cn C第二行：第二行：C1 P1(0) P1(1) P1(X1) C1 P1(0) P1(1) P1(X1) 0=X1=C/Ck0=X1=C/Ck 第第n n 行：行：Cn Pn(0) Pn(1) Pn(Xn) Cn Pn(0) Pn(1) Pn(Xn) 0=Xn=C/Cn0=Xn=C/Cn输入：输入：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 0.8

15、0.9 0.95 5 0.7 0.75 0.8 0.8 0.9 0.95输出：输出：0.63750.6375分析q设设f(i,j)f(i,j)表示将表示将j j的资金用到前的资金用到前i i项备用件中去的项备用件中去的最大可靠性，那么有最大可靠性，那么有q F(i,j)= F(i,j)=q maxF(i-1,jk maxF(i-1,jk* *Costi)Costi)* *Pi,kPi,kq 0=i=n, 0=j=C,0=kj div Cost(i) 0=i=n, 0=j=C,0=kj div Cost(i)q初始：初始： F(0,0)=0 F(0,0)=0q目的：目的： F(n,C) F(n,

16、C)q时间复杂度：时间复杂度：O(kO(k* *n n* *C)C)，这里，这里k k是常数因子，与数是常数因子，与数据相关据相关思索题思索题4：快餐问题：快餐问题q套餐由由套餐由由A个汉堡，个汉堡，B个薯条和个薯条和C个饮料组成个饮料组成q消费汉堡、薯条、饮料的时间为消费汉堡、薯条、饮料的时间为p1,p2,p3q有有N条流水线，条流水线，N=10，第，第i条流水线消费时间为条流水线消费时间为Tiq每条流水线都可消费汉堡、薯条和饮料每条流水线都可消费汉堡、薯条和饮料q每天汉堡、薯条和饮料个数不超越每天汉堡、薯条和饮料个数不超越100q如何安排消费使得消费套餐数量最多。如何安排消费使得消费套餐数

17、量最多。分析q对于每条流水线，它的消费时间是一定的，我们对于每条流水线，它的消费时间是一定的，我们假设知道了消费汉堡和薯条的个数，就很容易计假设知道了消费汉堡和薯条的个数，就很容易计算出消费饮料的个数。因此，算出消费饮料的个数。因此，q假设第假设第i条流水线消费了条流水线消费了i个汉堡，个汉堡，j个薯条个薯条,那么那么还能消费饮料个数为：还能消费饮料个数为：qk=(Ti-i*p1-j*p2)/p3动态规划q 设设f(x,i,j)表示前表示前x条流水线消费条流水线消费i个汉堡，个汉堡，j个薯条最多还能消费饮料个个薯条最多还能消费饮料个数。数。q 假设前假设前x-1条流水线只需消费条流水线只需消费

18、i汉堡，汉堡，j个薯条，消费的饮料为个薯条，消费的饮料为f(x-1,i,j)q 因此有第因此有第x条流水线必需消费了条流水线必需消费了i-i个汉堡，个汉堡，j-j个薯条，剩下的时间消个薯条，剩下的时间消费费k个饮料。个饮料。q 由于前由于前x条流水线消费的饮料条流水线消费的饮料=q 前前x-1条流水线消费的饮料条流水线消费的饮料 + 第第x条流水线消费的饮料条流水线消费的饮料q 所以有，所以有，f(x,i,j)=maxf(x-1,i,j)+k32*) (1*) (ppjjpiiTxk流水线资源分配图32*) (1*) (ppjjpiiTxk其中，思索？qf(x,i,j)=maxf(x-1,i,

19、j)+kq1=x=n=10,0=i=i=100, 0=j=j=100qk可以实时求出可以实时求出q时间复杂度为时间复杂度为10*1002*1002=109q显然超时！显然超时！优化求出最多能够消费多少套，减少不用要循环。求出最多能够消费多少套，减少不用要循环。淘汰一些没有意义形状，比如消费了过多第三种淘汰一些没有意义形状，比如消费了过多第三种物质，却没把前两种消费满。物质，却没把前两种消费满。让每条流水线大多数时间按成套时间消费，留下让每条流水线大多数时间按成套时间消费，留下一些时间进展动态规划，这样将在动态规划时，一些时间进展动态规划，这样将在动态规划时，极大地减少每种物品的产量从而极大地减少动态极大地减少每种物品的产量从而极大地减少动态规划的形状数。规划的形状数。阐明q 利用前两个优化根本可以出解利用前两个优化根本可以出解q 第第3个优化，对每条流水线进展动态规划的剩余时间多少比较难确定，个优化，对每条流水线进展动态规划的剩余时间多少比较难确定，否那么正确性难以保证，剩余时间越多，正确率越高，速度越慢。以否那么正确性难以保证，剩余时间越多，正确率越高，速度越慢。以下图是对第下图是对第3个优化的阐明：个优化的阐明