第25讲动态规划精选文档.ppt

第第2525讲动态规划讲动态规划1本讲稿第一页，共九十六页回顾：回顾：数字三角形数字三角形机器人捡垃圾机器人捡垃圾最大连续子序列和最大连续子序列和最长递增子序列最长递增子序列背包问题。背包问题。2本讲稿第二页，共九十六页简单的背包问题(0-1背包)设有种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，今从种物品中选取若干件，使其重量的和小于等于m，而价值的和为最大。N=100,M1000.输入数据：第一行两个数：物品总数，背包载重量M；两个数用空格分隔；第二行N个数,为种物品重量Wi(1000)；两个数用空格分隔；第三行N个数,为N种物品价值Vi(1000);两个数用空格分隔；输出数据：总价值；输入样例输入样例1：4 104 3 5 715 7 20 25输出样例输出样例1：35输入样例输入样例2：4 202 9 10 15 2 9 10 16 输出样例输出样例2：193本讲稿第三页，共九十六页0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量背包的容量0-10物物品品0-4编号1234容量4357价值15720254件物品件物品 背包容量：背包容量：10算法：算法：设设fi,j:从从1到到i件物品中选若取干件放到容量为件物品中选若取干件放到容量为j的背包中，的背包中，获得的最大价值。目标是：获得的最大价值。目标是：fn,m4本讲稿第四页，共九十六页用用fi,j表示在第到第表示在第到第i件物品中装入重量为件物品中装入重量为j的背包获得的最大价的背包获得的最大价值值fi,j=max fi-1,j ,fi-1,j-Wi+Vi (1=i=n,1=j=wi1)fi-1,j:不放第不放第i件物品获得的价值。件物品获得的价值。5本讲稿第五页，共九十六页主程序：主程序：fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);for i:=for i:=1 1 to n do to n do for j:=1 to m dofor j:=1 to m do begin begin fi,j:=fi-1,j;fi,j:=fi-1,j;/不选择第不选择第i i件物品件物品 if(j=wi)and(fi,j=wi)and(fi,jB2-C4-D3-E最短距离：最短距离：13倒推法：倒推法：10本讲稿第十页，共九十六页动态规划的术语：动态规划的术语：1、阶段：阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用阶段变量是离散的，用k k表示。表示。阶段的划分一般根据时间和空间来划分的。阶段的划分一般根据时间和空间来划分的。2、状态：、状态：某一阶段的出发位置成为状态，通常一个阶段有多个状态。某一阶段的出发位置成为状态，通常一个阶段有多个状态。状态通常可以用一个或一组数来描述，称为状态变量。状态通常可以用一个或一组数来描述，称为状态变量。3、决策：、决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。（行动）称为决策。描述决策的变量称决策变量描述决策的变量称决策变量 4、策略和最优策略、策略和最优策略 所有阶段的决策有序组合构成一个策略。所有阶段的决策有序组合构成一个策略。最优效果的策略叫最优策略。最优效果的策略叫最优策略。11本讲稿第十一页，共九十六页fkx=minfk+1yi+d x,yi状态转移方程：状态转移方程：由已求得的状态来求未知状态，递推关系式称为状态转移方程。由已求得的状态来求未知状态，递推关系式称为状态转移方程。X Xy y1 1y y2 2y yi iE EFx:xFx:x到终点的最短距离。目标是到终点的最短距离。目标是f f1 1AA倒推：倒推：12本讲稿第十二页，共九十六页fkx=minfk-1yi+d yi,xFx:Fx:起点到起点到x x最短距离。目标是最短距离。目标是f f5 5EE顺推：顺推：X Xy y1 1y y2 2y yi iA A13本讲稿第十三页，共九十六页结合题目看方程：顺推和倒推结合题目看方程：顺推和倒推14本讲稿第十四页，共九十六页一般形式：一般形式：U：状态；X：策略：策略顺推：顺推：fUk=optfUk-1+LUk-1,Xk-1 （LUk-1,Xk-1：状态状态Uk-1通过策略通过策略Xk-1到达状态到达状态Uk 的费用）的费用）初始初始fU1；结果：；结果：f(Un)15本讲稿第十五页，共九十六页一般形式：一般形式：U：状态；X：策略：策略倒推：fUk=optfUk+1+LUk,Xk （LUk,Xk：状态状态Uk通过策略通过策略Xk到达状态到达状态Uk+1 的费用）的费用）初始初始fUn；结果：；结果：f(U1)16本讲稿第十六页，共九十六页动态规划问题的特征动态规划问题的特征 :1 1、最优子结构、最优子结构 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。2 2、重叠子问题、重叠子问题 在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。17本讲稿第十七页，共九十六页3 3、无后效性原则、无后效性原则 “已经求得的状态值，不受未求的那些状态的影响”。后面阶段的状态只受前面阶段的状态的影响。对于任意两个状态，只能单向的进行转移。某个状态一旦被求出，以后不再会发生变化（不受后面的影响）。要求的状态在空间或时间上是有序的。18本讲稿第十八页，共九十六页最优子结构、重叠子问题、无后效性最优子结构、重叠子问题、无后效性阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5AB1B2C1C2C3C4D1D2D3E53163843855634319本讲稿第十九页，共九十六页有后效性有后效性:D1阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5AB1B2C1C2C3C4D1D2D3E5316384385564325252 220本讲稿第二十页，共九十六页拓扑图（有向无环图）拓扑图（有向无环图）无后效性无后效性21本讲稿第二十一页，共九十六页非拓扑图（可能有环）非拓扑图（可能有环）有后效性有后效性 a ab bc c？b bc ca a？abc5111122本讲稿第二十二页，共九十六页动态规划的条件：无后效性、最优子问题动态规划的条件：无后效性、最优子问题无后效性、最优子问题是否能满足与 状态的表示、阶段的划分、状态的转移有关23本讲稿第二十三页，共九十六页 1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；记忆化搜索（树型）、递推 4、根据计算最优值时得到的信息，构造一个最优解。设计动态规划法的步骤：设计动态规划法的步骤：24本讲稿第二十四页，共九十六页 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）.定量处理的过程也就是决策实施的过程.动态规划的关键：动态规划的关键：25本讲稿第二十五页，共九十六页fUn=初始值；for kn-1 downto 1 do 枚举阶段 for U取遍所有状态 do 枚举状态 for X取遍所有决策 do 枚举决策 fUk=optfUk+1+LUk,Xk；/LUk,Xk：状态Uk通过策略Xk到达状态Uk+1的费用输出：fU1:目标动态规划的一般倒推格式为：动态规划的一般倒推格式为：26本讲稿第二十六页，共九十六页fUfU1 1=初始值；初始值；for kfor k2 to n do 2 to n do 枚举每一个阶段枚举每一个阶段 for Ufor U取遍所有状态取遍所有状态 dodo for X for X取遍所有决策取遍所有决策 dodo fUfUk k=optfU=optfUk-1k-1+LU+LUk-1k-1,X,Xk-1k-1；/LU /LUk-1k-1,X,Xk-1k-1：状态状态U Uk-1k-1通过策略通过策略X Xk-1k-1到达状态到达状态U Uk k 的费用的费用输出：输出：fUfUn n:目标目标动态规划的一般顺推格式为：动态规划的一般顺推格式为：27本讲稿第二十七页，共九十六页贪心算法采用“自顶向下”的方式使用最优子结构的：先做选择，在当时看起来是最优的选择（只顾眼前利益），然后再求解选择的那个子问题。“先选择，再求解子问题”dp：“先寻找子问题的解，然后做出选择”。7 3 8 8 1 0 2 7 4 44 5 2 6 5“贪心算法贪心算法“和dp很相似，它使用的问题也具有最优子结构。显著区别：显著区别：28本讲稿第二十八页，共九十六页二、动态规划举例二、动态规划举例29本讲稿第二十九页，共九十六页【问题描述问题描述】总公司拥有高效生产设备总公司拥有高效生产设备M M台，准备分给下属的台，准备分给下属的N N个公司。各分公司个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。若获得这些设备，可以为国家提供一定的盈利。问：问：如何分配这如何分配这M M台设备才能使国家得到的盈利最大？求出最大盈利值。台设备才能使国家得到的盈利最大？求出最大盈利值。其中其中M=150,N=100M=150,N=100。分配原则：每个公司有权获得任意数目的设备。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数，但总台数不得超过总设备数M M。【输入输入】第一行两个数，第一个数是分公司数第一行两个数，第一个数是分公司数N N，第二个数是设备台数，第二个数是设备台数M M。接下来是一个接下来是一个N*MN*M的矩阵的矩阵A A，Ai,jAi,j是第是第i i个公司分配个公司分配j j台机器所能获台机器所能获得的盈利。得的盈利。0=Ai,j=10000=Ai,j=1000【输出输出】最大盈利值。最大盈利值。、机器分配、机器分配30本讲稿第三十页，共九十六页【样例输入样例输入】3 43 410 15 26 3010 15 26 3020 32 38 4320 32 38 4312 20 27 3512 20 27 35【样例输出样例输出】545431本讲稿第三十一页，共九十六页fi,j:前i个(1.i)公司分配j台机器获得的最大盈利。求如下的数组：f1,1,f1,2,f1,m f2,1,f2,2,f2,m fn,1,fn,2,fn,m目标：fn,m分析：分析：32本讲稿第三十二页，共九十六页1234110152630220323843312202735ai,j:第i个公司分j台机器的获利fi,j:前i个公司分配j台机器获得的最大盈利。0123400000010101526302020324248302032445433本讲稿第三十三页，共九十六页fi,j=maxfi-1,j-k+ai,k(1=i=n,1=j=m,0=k=j)初始：初始：f1,i:=a1,i i:1m目标：目标：fn,m动态转移方程：动态转移方程：34本讲稿第三十四页，共九十六页for i:=1 to m do f1,i:=a1,i;for i:=2 to n do for j:=1 to m do for k:=0 to j do fi,j:=max(fi,j,fi-1,j-k+ai,k);格式一：35本讲稿第三十五页，共九十六页for i:=1 to n do for j:=1 to m do for k:=0 to j do fi,j:=max(fi,j,fi-1,j-k+ai,k);格式二：36本讲稿第三十六页，共九十六页【问题描述问题描述】假设你想以最美观的方式布置花店的橱窗。你有假设你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时，你束花，每束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从1至至V顺序编号，顺序编号，V是花瓶的数目，编号为是花瓶的数目，编号为1的花瓶在最左边，编号为的花瓶在最左边，编号为V的花瓶在最右边。花束则可以移动，的花瓶在最右边。花束则可以移动，并且每束花用并且每束花用1至至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果如果Ij，则花束，则花束I必须放在花束必须放在花束j左边的花瓶中。左边的花瓶中。例如，假设杜鹃花的标识数为例如，假设杜鹃花的标识数为1，秋海棠的标识数为，秋海棠的标识数为2，康乃馨的标识数为，康乃馨的标识数为3，所有的花束在，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。馨左边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表示。不同搭配所具有的美学值，可以用下面式样的表格来表示。、花店橱窗布置（、花店橱窗布置（IOI99IOI99）37本讲稿第三十七页，共九十六页花 瓶12345花 束1、杜鹃花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都可以接受，但你只需输出其中一种摆放方式。假设条件（Asumption）1F100，其中F为花束的数量，花束编号从1至F。FV100，其中V是花瓶的数量。-50Aij50，其中Aij 是花束i在花瓶j中时的美学值。38本讲稿第三十八页，共九十六页【输入】第一行包含两个数：F、V。随后的F行中，每行包含V个整数，Aij即为输入文件中第（i+1）行中的第j个数。【输出】最大美学值。【样例输入】3 57 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20【样例输出】53样例说明：束花分别依次插在、号花瓶内。39本讲稿第三十九页，共九十六页花 瓶12345花 束1、杜鹃花72323-2、秋海棠-282833-3、康乃馨-242453fi，j=前i束花放入前j个花瓶内的最大美学价值（花i不一定必须插在瓶j内)目标:fn,m花 瓶12345花 束1、杜鹃花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020ai,jai,jfi,jfi,j方法一方法一40本讲稿第四十页，共九十六页分析：分析：ai,j=ai,j=花花i i放入放入j j瓶的美学价值。瓶的美学价值。fifi，j=j=前前i i束花放入前束花放入前j j个花瓶内的最大美学价值（个花瓶内的最大美学价值（花花i i不一定必须插在瓶不一定必须插在瓶j j内内）。）。计算计算fi,jfi,j有两种情况：有两种情况：1):1):花花i i放入第放入第j j个花瓶中：个花瓶中：fifi，j=fi-1,j-1+ai,jj=fi-1,j-1+ai,j 2):2):花花i i不放入第不放入第j j个花瓶中个花瓶中,只能放在前只能放在前j-1j-1个花瓶内：个花瓶内：fifi，j=fi,j-1j=fi,j-1动态转移方程：动态转移方程：fifi，j jmaxmaxfi-1,j-1+ai,jfi-1,j-1+ai,j，fi,j-1fi,j-1初始化：初始化：fi,i=a1,1+a2,2+ai,i;fi,i=a1,1+a2,2+ai,i;目标：目标：fn,mfn,m41本讲稿第四十一页，共九十六页容易理解的方法：f1,1:=a1,1;for i:=2 to n do fi,i:=fi-1,i-1+ai,i;/求对角线 for i:=2 to m-(n-1)do f1,i:=max(f1,i-1,a1,i);/求第一行 for i:=2 to n do for j:=i+1 to m-(n-i)do fi,j:=max(fi,j-1,fi-1,j-1+ai,j);程序实现时要根据程序实现时要根据方程方程和问题的和问题的实际意义实际意义，主要，主要边界边界情况情况花 瓶12345花 束1、杜鹃花72323-2、秋海棠-282833-3、康乃馨-24245342本讲稿第四十二页，共九十六页写法改进：写法改进：fillchar(f,sizeof(f),0);/至少保证第0行全部为0for i:=1 to n do fi,i-1:=-5001;/对角线下斜线为无穷小for i:=1 to n do for j:=i to m-(n-i)do fi,j:=max(fi,j-1,fi-1,j-1+ai,j);43本讲稿第四十三页，共九十六页分析：ai,j表示第i束花插到第j个花瓶中的价值；fi,j表示第i束花插到第j个花瓶后，也就是说：第i束花插在第个花瓶，前i-1束花插在前-个花瓶内所获得的价值和的最大值。动态转移方程：fi,jmaxfi-1,k+ai,j (i-1=k=j-1)枚举第i-1束花所在的花瓶k初始化：f0,0=0;fi,0=-(1=i=n)目标：maxfn,i (1=ifi,j then fi,j:=fi-1,k;inc(fi,j,ai,j);end;ans:=min;for i:=n to m do if fn,ians then ans:=fn,i;45本讲稿第四十五页，共九十六页输出方案：输出方案：fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);fillchar(path,sizeof(path),0);fillchar(path,sizeof(path),0);for i:=1 to n do for i:=1 to n do for j:=i to m-(n-i)do for j:=i to m-(n-i)do begin begin fi,j:=min;fi,j:=min;for k:=i-1 to j-1 do for k:=i-1 to j-1 do if fi-1,kfi,j then if fi-1,kfi,j then begin fi,j:=fi-1,k;pathi,j:=k;end;begin fi,j:=fi-1,k;pathi,j:=k;end;inc(fi,j,ai,j);inc(fi,j,ai,j);end;end;ans:=min;ans:=min;for i:=n to m do for i:=n to m do if fn,ians then if fn,ians then begin ans:=fn,i;last:=i;end;begin ans:=fn,i;last:=i;end;46本讲稿第四十六页，共九十六页dfs(n,last)dfs(n,last)procedure dfs(i,j:longint);procedure dfs(i,j:longint);begin begin if pathi,j0 then if pathi,j0 then begin begin dfs(i-1,pathi,j);dfs(i-1,pathi,j);write(j,);write(j,);end end else write(j,);else write(j,);end;end;47本讲稿第四十七页，共九十六页你刚刚继承了首珍贵的、没有发行的歌曲，它们由流行的演唱组录制。你的计划是选择其中一些歌曲来发行个唱片，每个唱片至多包含分钟的音乐，唱片中的歌曲之间不能重复。由于你是一个古典音乐的爱好者，所以你没办法区分这些歌曲的价值，你按照下面的标准作选择：1)这些唱片中的歌曲必须按它们写作的顺序排序。（如果第一个唱片录制了歌曲、，则第二个唱片只能从开始选择）2)包含歌曲的总数量尽可能的多。输入：第一行包含数值，（不大于的整数），下面包含首歌曲的长度，它们按写作的顺序排列，没有一首歌曲超出唱片的长度，而且不可能将所有歌曲都放在唱片中。输出：输出应是按照标准进行选择个唱片，所能包含的最多歌曲数目。样例：输入：5 6 44 3 4 4 5输出：43 3、制作唱片、制作唱片48本讲稿第四十八页，共九十六页用用aiai保存第保存第i i首歌曲的长度。首歌曲的长度。si,jsi,j用用1 1张盘可以保存张盘可以保存i i到到j j首歌曲之间最多的歌曲数目。首歌曲之间最多的歌曲数目。设设fi,j=fi,j=前前i i首歌用首歌用j j张盘可以录制的最多数量。张盘可以录制的最多数量。状态转移方程：状态转移方程：fi,j=maxfk-1,j-1+sk,i fi,j=maxfk-1,j-1+sk,i (j=k=i)(j=k=i)一部分是用一部分是用j-1j-1张盘把前张盘把前k-1k-1首歌能录制的最大数量，另一部分是用首歌能录制的最大数量，另一部分是用一张盘在第一张盘在第k k到第到第i i首歌之间能录制的数量。首歌之间能录制的数量。目标：目标：fn,mfn,m算法一：算法一：49本讲稿第四十九页，共九十六页实现实现1 1：fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);for i:=1 to n do for i:=1 to n do for j:=1 to m do for j:=1 to m do for k:=1 to i do for k:=1 to i do fi,j:=max(fi,j,fk-1,j-1+sk,i);fi,j:=max(fi,j,fk-1,j-1+sk,i);时间：时间：O(N2*M)50本讲稿第五十页，共九十六页求求si,jsi,j readln(n,v,m);readln(n,v,m);for i:=1 to n do read(ai);for i:=1 to n do read(ai);for i:=1 to n do /for i:=1 to n do /起点起点i i begin begin num:=0;/i num:=0;/i到到j j能用一张盘刻的最多歌曲数量能用一张盘刻的最多歌曲数量 b0:=0;sum0:=0;b0:=0;sum0:=0;for j:=i to n do/for j:=i to n do/终点终点j j begin begin k:=num;k:=num;while ajbk do /while ajbk do /插入排序插入排序i i到到j j的歌曲的歌曲 begin bk+1:=bk;sumk+1:=sumk+aj;dec(k);end;begin bk+1:=bk;sumk+1:=sumk+aj;dec(k);end;bk+1:=aj;sumk+1:=sumk+aj;bk+1:=aj;sumk+1:=sumk+aj;if sumnum+1=v then inc(num);if sumnum+1=v then inc(num);si,j:=num;si,j:=num;end;end;end;end;51本讲稿第五十一页，共九十六页时间：时间：O(N3+N2*M)空间：空间：N*Mfi,jfi,j与第与第j-1j-1列有关列有关52本讲稿第五十二页，共九十六页XXXXXXXXXXXXXXXXXXXX1 15 510101 110105 51 11 153本讲稿第五十三页，共九十六页优化：减少状态和决策；按列优先求优化：减少状态和决策；按列优先求 fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);for j:=1 to m do for j:=1 to m do for i:=j to n-(m-j)do for i:=j to n-(m-j)do for k:=j to i do for k:=j to i do fi,j:=max(fi,j,fk-1,j-1+sk,i);fi,j:=max(fi,j,fk-1,j-1+sk,i);54本讲稿第五十四页，共九十六页算法算法2：fi,j,k:=max fi-1,j,k;/不刻录第不刻录第i首歌首歌 fi-1,j,k-ai+1;/aik)and(j=1)目标：目标：fn,m,0 或或 fn,m-1,tfi,j,k:前前i首歌，首歌，j张没用的光盘，另加一张光盘，有张没用的光盘，另加一张光盘，有k分钟未使用。分钟未使用。可以录制的歌曲的最大数量。可以录制的歌曲的最大数量。55本讲稿第五十五页，共九十六页for i:=1 to n do for j:=0 to m do for k:=0 to t do begin fi,j,k:=fi-1,j,k;if(ai=k)and(fi,j,kk)and(j=1)and (fi,j,kfi-1,j-1,t-ai+1)then fi,j,k:=fi-1,j-1,t-ai+1;end;writeln(fn,m,0);时间：时间：O(n*m*t)空间：空间：N*M*T56本讲稿第五十六页，共九十六页思考：最多能录制多长时间的歌曲？57本讲稿第五十七页，共九十六页某公司要出口一批货物，货物的种类是(50)，不同的货物用不同的集装箱装盛，它们的重量依次为a1,a2,an，（ai20），由运送带按a1,a2,an顺序依次运送到船边，现有m(10)艘船可共使用来运载这批货物，每条船的最大载重量w(100)，在装船时，按照传送带传送货物的顺序向船上搬运货物，由于传动带在传送过程中始终不停止，并且速度很快，一旦错过不选某件货物，就无法再搬到船上，如：第条船装了货物a1,a3，则第条船只能从a开始装，即a2被错过，无法再被装船。而且装船的规则是，只有一条船装完后才能装下一条船。没有一件货物的重量超过船的载重量。编程：选择哪货物装到船上使这条船所能装载货物的最大重量（某件货物要么装要么不装）。输入：第一行：，m，w第二行：a1,a2,an输出：条船所能运载货物的最大重量。样例：样例：输入：输入：210输出：输出：（选择（选择 8 4 5）7 7、集装箱运输、集装箱运输58本讲稿第五十八页，共九十六页提示：求货物的最大载重量，而不是求最多能装多少件货物！59本讲稿第五十九页，共九十六页算法一：算法一：fi,j,k:前前i件货物，件货物，j条船，另加剩余容量为条船，另加剩余容量为k的一条船能装的的一条船能装的最大重量。最大重量。fi,j,k:=max fi-1,j,k;/不装第不装第i件货物件货物 fi-1,j,k-ai+ai;/aik)and(j0)fn,m,0 或或 fn,m-1,w60本讲稿第六十页，共九十六页for i:=1 to n dofor i:=1 to n do for j:=0 to m-1 do for j:=0 to m-1 do for k:=0 to w do for k:=0 to w do begin begin fi,j,k:=fi-1,j,k;fi,j,k:=fi-1,j,k;if k=ai then if k=ai then fi,j,k:=max(fi,j,k,fi-1,j,k-ai+ai);fi,j,k:=max(fi,j,k,fi-1,j,k-ai+ai);if(kai)and(j0)then if(kai)and(j0)then fi,j,k:=max(fi,j,k,fi-1,j-1,w-ai+ai);fi,j,k:=max(fi,j,k,fi-1,j-1,w-ai+ai);end;end;时间：时间：O(n*m*W)空间：空间：N*M*W61本讲稿第六十一页，共九十六页分析：分析：设设fi,j:前前i件货物用件货物用j条船的最大载重量。条船的最大载重量。si,j:一条船在第一条船在第i到第到第j件货物选择装的最大载重量件货物选择装的最大载重量 动态转移方程：动态转移方程：fi,j=maxfk,j-1+sk+1,i (0=k=tx)and(dx,y=tx)and(dx,y=aj then if k=aj then dj,k:=max(dj,k,dj-1,k-aj+aj);dj,k:=max(dj,k,dj-1,k-aj+aj);end;end;si,j:=dj,w;/si,j:=dj,w;/从从i i开始到开始到j j一条船的最大载重货物量一条船的最大载重货物量 end;end;end;end;求求si,j方法方法2：时间时间:O(n2*w)65本讲稿第六十五页，共九十六页动态规划求解：动态规划求解：for i:=1 to n do阶段阶段 for j:=1 to m do状态状态 for k:=0 to i-1 do策略策略 fi,j:=max(fi,j,fk,j-1+sk+1,i);总时间：总时间：O(n2*w+n2*m)66本讲稿第六十六页，共九十六页8 8、最大、最大mm子段和问题子段和问题给定由n个整数（可能为负整数）组成的序列a1,a2,.an，以及一个正整数m，要求确定序列a1,a2,.an的m个不相交子段，使这m个子段的总合达到最大。输入：第一行：N，m。n=1000,m=10 第二行：a1,a2,.an。中间一个空格。ai=(-30000,30000)输出：M个子段的最大和。样例输入：样例输入：10 2-1 3 -1 4 -2 -3 5 -2 3 -1样例输出：样例输出：1267本讲稿第六十七页，共九十六页分析：分析：m=1m=1的情况的情况令令FiFi：以：以aiai为终点（右边界）的子序列的最大和。为终点（右边界）的子序列的最大和。FI=maxak+ak+1+aI(1=k=I)FI=maxak+ak+1+aI(1=k=I)状态转移方程：状态转移方程：fi=maxfi-1+ai,ai fi=maxfi-1+ai,ai：=maxfi-1,0+ai.=maxfi-1,0+ai.即看即看fifi的正负的正负初始：初始：f1=a1f1=a1目标：目标：maxfi 1=i=nmaxfi 1=i=n求最大连续子序列的和求最大连续子序列的和68本讲稿第六十八页，共九十六页算法算法1 1：令令fi,j:1fi,j:1到第到第i i数中，取数中，取j j段的最大和。段的最大和。fi,j=maxfk,j-1+dk+1,ifi,j=maxfk,j-1+dk+1,i (j-1=k=i-1)(j-1=k1m1的情况的情况69本讲稿第六十九页，共九十六页求求di,j:di,j:动规动规for i:=1 to n dofor i:=1 to n do begin begin di,i:=ai;sum:=ai;max:=ai;di,i:=ai;sum:=ai;max:=ai;for j:=i+1 to n do for j:=i+1 to n do begin begin sum:=fmax(sum+aj,aj);sum:=fmax(sum+aj,aj);max:=fmax(max,sum);max:=fmax(max,sum);di,j:=max;di,j:=max;end;end;end;end;时间：时间：O（N2）70本讲稿第七十页，共九十六页求求fi,jfi,j f1,1:=a1;for i:=2 to m do fi,i:=fi-1,i-1+ai;for j:=1 to m do for i:=j+1 to n do begin fi,j:=-maxlongint;for k:=j-1 to i-1 do fi,j:=fmax(fi,j,fk,j-1+dk+1,i);end;时间：时间：O（N2*M）71本讲稿第七十一页，共九十六页算法算法2 2：令令fi,j:1fi,j:1到第到第i i数中，取数中，取j j段的最大和，段的最大和，并且第并且第j j个子段中包含个子段中包含aIaI。则目标是：则目标是：maxfI,m(m=I=n).maxfI,m(m=I=n).第第j j段有两种情况：段有两种情况：第第j j段中只含有段中只含有aIaI一个数，即一个数，即aIaI独自一段：独自一段：fI,j=maxfk,j-1+aIfI,j=maxfk,j-1+aI（j-1=k=I-1j-1=k=I-1）；）；第第j j段中至少含段中至少含aI-1,aI-1,即即即即aIaI不是独自一段。不是独自一段。fI,j=fI-1,fI,j=fI-1,j j+aI+aI；fI,j=maxfI-1,j+aIfI,j=maxfI-1,j+aI，maxfk,j-1+aI maxfk,j-1+aI （j-1=k=I-1j-1=k=I-1）72本讲稿第七十二页，共九十六页f1,1:=a1;f1,1:=a1;for i:=2 to m do fi,i:=fi-1,i-1+ai;for i:=2 to m do fi,i:=fi-1,i-1+ai;for j:=1 to m dofor j:=1 to m do for i:=j+1 to n do for i:=j+1 to n do begin begin fi,j:=fi-1,j+ai;fi,j:=fi-1,j+ai;for k:=j-1 to i-1 do for k:=j-1 to i-1 do fi,j:=fmax(fi,j,fk,j-1+ai);fi,j:=fmax(fi,j,fk,j-1+ai);end;end;ans:=-maxlongint;ans:=-maxlongint;for i:=m to n do ans:=fmax(ans,fi,m);for i:=m to n do ans:=fmax(ans,fi,m);时间：时间：O（N2*M）73本讲稿第七十三页，共九十六页有一个由数字0,1，2，.，9组成的数字串（长度不超过200），问如何将M(0=M=20)个加号(“+”)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。输入格式数字串在输入文件的第一行行首（数字串中间无空格且不折行），的值在输入文件的第二行行首。输出格式所求得的最小和的精确值。输入输出举例输 入：82363983742 3输 出：2170 9 9、最小加法表达式、最小加法表达式74本讲稿第七十四页，共九十六页分析：分析：