第25讲动态规划PPT讲稿.ppt

《第25讲动态规划PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第25讲动态规划PPT讲稿.ppt（96页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第2525讲动态规划讲动态规划1第1页，共96页，编辑于2022年，星期一回顾：回顾：数字三角形数字三角形机器人捡垃圾机器人捡垃圾最大连续子序列和最大连续子序列和最长递增子序列最长递增子序列背包问题。背包问题。2第2页，共96页，编辑于2022年，星期一简单的背包问题(0-1背包)设有种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，今从种物品中选取若干件，使其重量的和小于等于m，而价值的和为最大。N=100,M1000.输入数据：第一行两个数：物品总数，背包载重量M；两个数用空格分隔；第二行N个数,为种物品重量Wi(1000)；两个数用空格分隔；第三行N个数,为N种物品

2、价值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第3页，共96页，编辑于2022年，星期一0123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量背包的容量0-10物物品品0-4编号1234容量4357价值15720254件物品件物品 背包容量：背包容量：

3、10算法：算法：设设fi,j:从从1到到i件物品中选若取干件放到容量为件物品中选若取干件放到容量为j的背包中，获得的的背包中，获得的最大价值。目标是：最大价值。目标是：fn,m4第4页，共96页，编辑于2022年，星期一用用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第5页，共96页，编辑于2022年，星期一主程序：主程序：fillchar(f,sizeof(f),0);f

4、illchar(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第10页，共96页，编辑于2022年，星期一动态规划的术语：动态规划的术语：1、阶段：阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一把所给求解问题的过程恰当地分成若

5、干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用变量。在多数情况下，阶段变量是离散的，用k k表示。表示。阶段的划分一般根据时间和空间来划分的。阶段的划分一般根据时间和空间来划分的。2、状态：、状态：某一阶段的出发位置成为状态，通常一个阶段有多个状态。某一阶段的出发位置成为状态，通常一个阶段有多个状态。状态通常可以用一个或一组数来描述，称为状态变量。状态通常可以用一个或一组数来描述，称为状态变量。3、决策：、决策：一个阶段的状态给定以后，从该状态

6、演变到下一阶段某个状态的一种选择（行动）一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。称为决策。描述决策的变量称决策变量描述决策的变量称决策变量 4、策略和最优策略、策略和最优策略 所有阶段的决策有序组合构成一个策略。所有阶段的决策有序组合构成一个策略。最优效果的策略叫最优策略。最优效果的策略叫最优策略。11第11页，共96页，编辑于2022年，星期一fkx=minfk+1yi+d x,yi状态转移方程：状态转移方程：由已求得的状态来求未知状态，递推关系式称为状态转移方程。由已求得的状态来求未知状态，递推关系式称为状态转移方程。X Xy y1 1y y2 2

7、y yi iE EFx:xFx:x到终点的最短距离。目标是到终点的最短距离。目标是f f1 1AA倒推：倒推：12第12页，共96页，编辑于2022年，星期一fkx=minfk-1yi+d yi,xFx:Fx:起点到起点到x x最短距离。目标是最短距离。目标是f f5 5EE顺推：顺推：X Xy y1 1y y2 2y yi iA A13第13页，共96页，编辑于2022年，星期一结合题目看方程：顺推和倒推结合题目看方程：顺推和倒推14第14页，共96页，编辑于2022年，星期一一般形式：一般形式：U：状态；X：策略：策略顺推：顺推：fUk=optfUk-1+LUk-1,Xk-1 （LUk-1

8、,Xk-1：状态状态Uk-1通过策略通过策略Xk-1到达状态到达状态Uk 的费用）的费用）初始初始fU1；结果：；结果：f(Un)15第15页，共96页，编辑于2022年，星期一一般形式：一般形式：U：状态；X：策略：策略倒推：fUk=optfUk+1+LUk,Xk （LUk,Xk：状态状态Uk通过策略通过策略Xk到达状态到达状态Uk+1 的费用）的费用）初始初始fUn；结果：；结果：f(U1)16第16页，共96页，编辑于2022年，星期一动态规划问题的特征动态规划问题的特征 :1 1、最优子结构、最优子结构 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理

9、。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。2 2、重叠子问题、重叠子问题 在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。17第17页，共96页，编辑于2022年，星期一3 3、无后效性原则、无后效性原则 “已经求得的状态值，不受未求的那些状态的影响”。后面阶段的状态只受前面阶段的状态的

10、影响。对于任意两个状态，只能单向的进行转移。某个状态一旦被求出，以后不再会发生变化（不受后面的影响）。要求的状态在空间或时间上是有序的。18第18页，共96页，编辑于2022年，星期一最优子结构、重叠子问题、无后效性最优子结构、重叠子问题、无后效性阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5AB1B2C1C2C3C4D1D2D3E53163843855634319第19页，共96页，编辑于2022年，星期一有后效性有后效性:D1阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5AB1B2C1C2C3C4D1D2D3E5316384385564325252 220第20页，共96页，编辑于

11、2022年，星期一拓扑图（有向无环图）拓扑图（有向无环图）无后效性无后效性21第21页，共96页，编辑于2022年，星期一非拓扑图（可能有环）非拓扑图（可能有环）有后效性有后效性 a ab bc c？b bc ca a？abc5111122第22页，共96页，编辑于2022年，星期一动态规划的条件：无后效性、最优子问题动态规划的条件：无后效性、最优子问题无后效性、最优子问题是否能满足与 状态的表示、阶段的划分、状态的转移有关23第23页，共96页，编辑于2022年，星期一 1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；记忆化

12、搜索（树型）、递推 4、根据计算最优值时得到的信息，构造一个最优解。设计动态规划法的步骤：设计动态规划法的步骤：24第24页，共96页，编辑于2022年，星期一 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）.定量处理的过程也就是决策实施的过程.动态规划的关键：动态规划的关键：25第25页，共96页，编辑于2022年，星期一fUn=初始值；for kn-1 downto 1 do 枚举阶段 for U取遍所有状态 do 枚举状态 for X取遍所有决策 do 枚举决策 fUk=o

13、ptfUk+1+LUk,Xk；/LUk,Xk：状态Uk通过策略Xk到达状态Uk+1的费用输出：fU1:目标动态规划的一般倒推格式为：动态规划的一般倒推格式为：26第26页，共96页，编辑于2022年，星期一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 U

14、k-1k-1通过策略通过策略X Xk-1k-1到达状态到达状态U Uk k 的费用的费用输出：输出：fUfUn n:目标目标动态规划的一般顺推格式为：动态规划的一般顺推格式为：27第27页，共96页，编辑于2022年，星期一贪心算法采用“自顶向下”的方式使用最优子结构的：先做选择，在当时看起来是最优的选择（只顾眼前利益），然后再求解选择的那个子问题。“先选择，再求解子问题”dp：“先寻找子问题的解，然后做出选择”。7 3 8 8 1 0 2 7 4 44 5 2 6 5“贪心算法贪心算法“和dp很相似，它使用的问题也具有最优子结构。显著区别：显著区别：28第28页，共96页，编辑于2022年，

15、星期一二、动态规划举例二、动态规划举例29第29页，共96页，编辑于2022年，星期一【问题描述问题描述】总公司拥有高效生产设备总公司拥有高效生产设备M M台，准备分给下属的台，准备分给下属的N N个公司。各分公司个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。若获得这些设备，可以为国家提供一定的盈利。问：问：如何分配这如何分配这M M台设备才能使国家得到的盈利最大？求出最大盈利值。台设备才能使国家得到的盈利最大？求出最大盈利值。其中其中M=150,N=100M=150,N=100。分配原则：每个公司有权获得任意数目的设备。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总

16、设备数，但总台数不得超过总设备数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第30页，共96页，编辑于2022年，星期一【样例输入样例输入】3 43 410 15 26 3010 15 26 3020 32 38 4320 32 38 4312

17、20 27 3512 20 27 35【样例输出样例输出】545431第31页，共96页，编辑于2022年，星期一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第32页，共96页，编辑于2022年，星期一1234110152630220323843312202735ai,j:第i个公司分j台机器的获利fi,j:前i个公司分配j台机器获得的最大盈利。0123400000010101526302020324248302032445433第33页，共96页，

18、编辑于2022年，星期一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第34页，共96页，编辑于2022年，星期一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第35页，共96页，编辑于2022年，星期一for i:=1 to n do for j:=1 to m do for

19、k:=0 to j do fi,j:=max(fi,j,fi-1,j-k+ai,k);格式二：格式二：36第36页，共96页，编辑于2022年，星期一【问题描述问题描述】假设你想以最美观的方式布置花店的橱窗。你有假设你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时，你至少有束花，每束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从1至至V顺序编号，顺序编号，V是是花瓶的数目，编号为花瓶的数目，编号为1的花瓶在最左边，编号为的花瓶在最左边，编号为V的花瓶

20、在最右边。花束则可以移动，并且每束的花瓶在最右边。花束则可以移动，并且每束花用花用1至至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果Ij，则，则花束花束I必须放在花束必须放在花束j左边的花瓶中。左边的花瓶中。例如，假设杜鹃花的标识数为例如，假设杜鹃花的标识数为1，秋海棠的标识数为，秋海棠的标识数为2，康乃馨的标识数为，康乃馨的标识数为3，所有的花束在放，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放

21、在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以

22、用下面式样的表格来表示。美学值，可以用下面式样的表格来表示。、花店橱窗布置（、花店橱窗布置（IOI99IOI99）37第37页，共96页，编辑于2022年，星期一花 瓶12345花 束1、杜鹃花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都可以接受，但你只需输出其中一种摆放方式。假设条件（Asumption）1F100，其中F为花束的数量，

23、花束编号从1至F。FV100，其中V是花瓶的数量。-50Aij50，其中Aij 是花束i在花瓶j中时的美学值。38第38页，共96页，编辑于2022年，星期一【输入】第一行包含两个数：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第39页，共96页，编辑于2022年，星期一花 瓶12345花 束1、杜鹃花72323-2、秋海棠-282833-3、康乃馨-242453fi，j=

24、前i束花放入前j个花瓶内的最大美学价值（花i不一定必须插在瓶j内)目标:fn,m花 瓶12345花 束1、杜鹃花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020ai,jai,jfi,jfi,j方法一方法一40第40页，共96页，编辑于2022年，星期一分析：分析：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

25、放入第放入第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第41页，共96页，编辑于2022年，星期一容易理解的方法：f1,1:=

26、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第42页，共96页，编辑于2022年，星期一写法改进：写法

27、改进：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第43页，共96页，编辑于2022年，星期一分析：ai,j表示第i束花插到第j个花瓶中的价值；fi,j表示第i束花插到第j个花瓶后，也就是说：第i束花插在第个花瓶，前i-1束花插在前-个花瓶内所获得的价值和的最大值。动态转移方程：fi,jmaxfi-1,k+ai,j (i-1=k=j-1)枚

28、举第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第45页，共96页，编辑于2022年，星期一输出方案：输出方案：fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);fillchar(path,sizeof(path),0);fillchar(path,sizeof(path),0);for i:=1 to

29、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:=mi

30、n;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第46页，共96页，编辑于2022年，星期一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);d

31、fs(i-1,pathi,j);write(j,);write(j,);end end else write(j,);else write(j,);end;end;47第47页，共96页，编辑于2022年，星期一你刚刚继承了首珍贵的、没有发行的歌曲，它们由流行的演唱组录制。你的计划是选择其中一些歌曲来发行个唱片，每个唱片至多包含分钟的音乐，唱片中的歌曲之间不能重复。由于你是一个古典音乐的爱好者，所以你没办法区分这些歌曲的价值，你按照下面的标准作选择：1)这些唱片中的歌曲必须按它们写作的顺序排序。（如果第一个唱片录制了歌曲、，则第二个唱片只能从开始选择）2)包含歌曲的总数量尽可能的多。输入：第一

32、行包含数值，（不大于的整数），下面包含首歌曲的长度，它们按写作的顺序排列，没有一首歌曲超出唱片的长度，而且不可能将所有歌曲都放在唱片中。输出：输出应是按照标准进行选择个唱片，所能包含的最多歌曲数目。样例：输入：5 6 44 3 4 4 5输出：43 3、制作唱片、制作唱片48第48页，共96页，编辑于2022年，星期一用用aiai保存第保存第i i首歌曲的长度。首歌曲的长度。si,jsi,j用用1 1张盘可以保存张盘可以保存i i到到j j首歌曲之间最多的歌曲数目。首歌曲之间最多的歌曲数目。设设fi,j=fi,j=前前i i首歌用首歌用j j张盘可以录制的最多数量。张盘可以录制的最多数量。状态

33、转移方程：状态转移方程：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第49页，共96页，编辑于2022年，星期一实现实现1 1：fillchar(f,sizeof(f),0);fillchar(f,sizeof(f),0);for i:=1 to n do for i

34、:=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第50页，共96页，编辑于2022年，星期一求求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

35、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

36、(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第51页，共96页，编辑于2022年，星期一时间：时间：O(N3+N2*M)空间：空间：N*Mfi,jfi,j与第与第j-1j-1列有关列有关52第52页，共96页，编辑于2022年，星期一XXXXXXXXXXXXXXXXXXXX1 15 510101 110105 51 11 153第53页，

37、共96页，编辑于2022年，星期一优化：减少状态和决策；按列优先求优化：减少状态和决策；按列优先求 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第54页，共96页，编辑于2022年，星期一算法算法2：

38、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第55页，共96页，编辑于2022年，星期一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)a

39、nd (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第56页，共96页，编辑于2022年，星期一思考：最多能录制多长时间的歌曲？57第57页，共96页，编辑于2022年，星期一某公司要出口一批货物，货物的种类是(50)，不同的货物用不同的集装箱装盛，它们的重量依次为a1,a2,an，（ai20），由运送带按a1,a2,an顺序依次运送到船边，现有m(10)艘船可共使用来运载这批货物，每条船的最大载重量w(100)，在装船时，按照传送带传送货物的

40、顺序向船上搬运货物，由于传动带在传送过程中始终不停止，并且速度很快，一旦错过不选某件货物，就无法再搬到船上，如：第条船装了货物a1,a3，则第条船只能从a开始装，即a2被错过，无法再被装船。而且装船的规则是，只有一条船装完后才能装下一条船。没有一件货物的重量超过船的载重量。编程：选择哪货物装到船上使这条船所能装载货物的最大重量（某件货物要么装要么不装）。输入：第一行：，m，w第二行：a1,a2,an输出：条船所能运载货物的最大重量。样例：样例：输入：输入：210输出：输出：（选择（选择 8 4 5）7 7、集装箱运输、集装箱运输58第58页，共96页，编辑于2022年，星期一提示：求货物的最大

41、载重量，而不是求最多能装多少件货物！59第59页，共96页，编辑于2022年，星期一算法一：算法一：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第60页，共96页，编辑于2022年，星期一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 t

42、o 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)

43、空间：空间：N*M*W61第61页，共96页，编辑于2022年，星期一分析：分析：设设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;/

44、从从i i开始到开始到j j一条船的最大载重货物量一条船的最大载重货物量 end;end;end;end;求求si,j方法方法2：时间时间:O(n2*w)65第65页，共96页，编辑于2022年，星期一动态规划求解：动态规划求解：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第66页，共96页，编辑于2022年，星期一8 8、最大、最大mm子段和问题子段和问题给定由n个整数（可能为负整数）组成的序列a1,a2

45、,.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第67页，共96页，编辑于2022年，星期一分析：分析：m=1m=1的情况的情况令令FiFi：以：以aiai为终点（右边界）的子序列的最大和。为终点（右边界）的子序列的最大和。FI=maxak+ak+1+aI(1=k=I)FI=maxak+ak

46、+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第68页，共96页，编辑于2022年，星期一算法算法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

47、=k1m1的情况的情况69第69页，共96页，编辑于2022年，星期一求求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;

48、end;end;end;时间：时间：O（N2）70第70页，共96页，编辑于2022年，星期一求求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第71页，共96页，编辑于2022年，星期一算法算法2 2：令令fi,j:1fi,j:1到第到第i i数中，取数中，取j j段的最大和

49、，段的最大和，并且第并且第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

50、+aI，maxfk,j-1+aI maxfk,j-1+aI （j-1=k=I-1j-1=k=I-1）72第72页，共96页，编辑于2022年，星期一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 fo