《第25讲：动态规划》由会员分享，可在线阅读，更多相关《第25讲：动态规划（96页珍藏版）》请在金锄头文库上搜索。
1、动动 态态 规规 划划2010/06/261回顾：回顾：数字三角形数字三角形机器人捡垃圾机器人捡垃圾最大连续子序列和最大连续子序列和最长递增子序列最长递增子序列背包问题。背包问题。2简单的背包问题(0-1背包) 设有种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，今从种物品中选取若干件，使其重量的和小于等于m，而价值的和为最大。N=100,M1000.输入数据：第一行两个数：物品总数，背包载重量M；两个数用空格分隔；第二行N个数,为种物品重量Wi(1000)；两个数用空格分隔；第三行N个数,为N种物品价值Vi(1000); 两个数用空格分隔；输出数据： 总价值；输入样例输
2、入样例1：4 104 3 5 715 7 20 25输出样例输出样例1：35输入样例输入样例2：4 202 9 10 15 2 9 10 16 输出样例输出样例2：1930 01 12 23 34 45 56 67 78 89 910100 00 00 00 00 00 00 00 00 00 00 00 01 10 00 00 00 015151515151515151515151515152 20 00 00 07 715151515151522222222222222223 30 00 00 07 715152020202022222727353535354 40 00 00 07 71
3、515202020202525272735353535背包的容量背包的容量0-10物物品品0-4编号编号1 12 23 34 4容量容量4 43 35 57 7价值价值15157 7202025254件物品件物品 背包容量：背包容量：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=
4、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,jfi,j:=fi-1,j;:=fi-1,j;/不选择第不选择第i i件物品件物品 if (j=if (j=wiwi) and () and (fi,jfi,jfi-1,j-wi+vi) /B2-C4-D3-E最短距离：最短距离：
5、13倒推法：倒推法：10动态规划的术语：动态规划的术语： 1、 阶段：阶段： 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量按一定的次序去求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用称为阶段变量。在多数情况下，阶段变量是离散的，用k k表示。表示。 阶段的划分一般根据时间和空间来划分的。阶段的划分一般根据时间和空间来划分的。 2、状态：、状态： 某一阶段的出发位置成为状态，通常一个阶段有多个状态。某一阶段的出发位置成
6、为状态，通常一个阶段有多个状态。 状态通常可以用一个或一组数来描述，称为状态变量。状态通常可以用一个或一组数来描述，称为状态变量。 3、决策：、决策： 一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。种选择（行动）称为决策。描述决策的变量称决策变量描述决策的变量称决策变量 4、策略和最优策略、策略和最优策略 所有阶段的决策有序组合构成一个策略。所有阶段的决策有序组合构成一个策略。 最优效果的策略叫最优策略。最优效果的策略叫最优策略。11fkx=minfk+1yi+d x,yi状态转移方程：状态转移方程：
7、由已求得的状态来求未知状态，递推关系式称为状态转移方程。由已求得的状态来求未知状态，递推关系式称为状态转移方程。X Xy y1 1y y2 2y yi iE EFx:xFx:x到终点的最短距离。目标是到终点的最短距离。目标是f f1 1AA倒推：倒推：12fkx=minfk-1yi+d yi,xFxFx: :起点到起点到x x最短距离。目标是最短距离。目标是f f5 5EE顺推：顺推：X Xy y1 1y y2 2y yi iA A13结合题目看方程：顺推和倒推结合题目看方程：顺推和倒推14一般形式：一般形式： U：状态； X：策略：策略顺推：顺推：fUk=optfUk-1+LUk-1,Xk-
8、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、最优子结构、最优子结构 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。 最优子结构也可以理解为“整体最优则局部最优”。反之
9、不一定成立。 2 2、重叠子问题、重叠子问题 在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题 。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。 动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。 173 3、无后效性原则、无后效性原则 “已经求得的状态值，不受未求的那些状态的影响”。 后面阶段的状态只受前面阶段的状态的影响。 对于任意两个状态，只能单向的进行转移。 某个状态一旦被求出，以后不再会发生变化
10、（不受后面的影响）。 要求的状态在空间或时间上是有序的。18最优子结构、重叠子问题、无后效性最优子结构、重叠子问题、无后效性阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5AB1B2C1C2C3C4D1D2D3E53163843855634319有后效性有后效性:D1阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段5AB1B2C1C2C3C4D1D2D3E5316384385564325252 220拓扑图（有向无环图）拓扑图（有向无环图）无后效性无后效性21非拓扑图（可能有环）非拓扑图（可能有环）有后效性有后效性 a ab bc c ？ b bc ca a？ abc5111122动态规划的
11、条件：无后效性、最优子问题动态规划的条件：无后效性、最优子问题无后效性、最优子问题是否能满足与 状态的表示、阶段的划分、状态的转移有关23 1、找出最优解的性质，并刻画其结构特征； 2、递归地定义最优值（写出动态规划方程）； 3、以自底向上的方式计算出最优值； 记忆化搜索（树型）、递推 4、根据计算最优值时得到的信息，构造一个最优解。设计动态规划法的步骤：设计动态规划法的步骤：24 状态转移方程的构造是动态规划过程中最重要的一步,也是最难的一步.对于大多数的动态规划,寻找状态转移方程有一条十分高效的通道,就是寻找变化中的不变量（已经求得的值）. 定量处理的过程也就是决策实施的过程.动态规划的关
12、键：动态规划的关键：25fUn=初始值；for kn-1 downto 1 do 枚举阶段 for U取遍所有状态 do 枚举状态 for X取遍所有决策 do 枚举决策 fUk=optfUk+1+LUk,Xk； /LUk,Xk：状态Uk通过策略Xk到达状态Uk+1的费用输出：fU1:目标动态规划的一般倒推格式为：动态规划的一般倒推格式为：26fUfU1 1=初始值初始值；for kfor k2 to n do 2 to n do 枚举每一个阶段枚举每一个阶段 for Ufor U取遍所有状态取遍所有状态 dodo for X for X取遍所有决策取遍所有决策 dodo fUfUk k=op
13、tfU=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“贪心算法贪心算法
14、“和dp很相似，它使用的问题也具有最优子结构。显著区别：显著区别：28二、动态规划举例二、动态规划举例29【问题描述问题描述】总公司拥有高效生产设备总公司拥有高效生产设备M M台，准备分给下属的台，准备分给下属的N N个公司。各分公司个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。若获得这些设备，可以为国家提供一定的盈利。问：问：如何分配这如何分配这M M台设备才能使国家得到的盈利最大？求出最大盈利值。台设备才能使国家得到的盈利最大？求出最大盈利值。其中其中M=150,N=100M=150,N=100。分配原则：每个公司有权获得任意数目的设备。分配原则：每个公司有权获得任意数目的设备
15、，但总台数不得超过总设备数，但总台数不得超过总设备数M M。【输入输入】第一行两个数，第一个数是分公司数第一行两个数，第一个数是分公司数N N，第二个数是设备台数，第二个数是设备台数M M。接下来是一个接下来是一个N*MN*M的矩阵的矩阵A A，Ai,jAi,j 是第是第i i个公司分配个公司分配j j台机器所能获台机器所能获得的盈利。得的盈利。0=0=Ai,jAi,j=1000=1000【输出输出】最大盈利值。最大盈利值。、机器分配、机器分配30【样例输入样例输入】3 43 410 15 26 3010 15 26 3020 32 38 4320 32 38 4312 20 27 3512
16、20 27 35【样例输出样例输出】545431fi,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分析：分析：321 12 23 34 41 110101515262630302 220203232383843433 31212202027273535ai,j:第i个公司分j台机器的获利fi,j:前i个公司分配j台机器获得的最大盈利。0 01 12 23 34 40 00 00 00 00 00 01 10 010101515262630302 20 02020323
17、2424248483 30 0202032324444545433fi,j=maxfi-1,j-k+ai,k (1=i=n,1=j=m,0=k=j)初始：初始：f1,i:=a1,i i:1m目标：目标：fn,m动态转移方程：动态转移方程：34for 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);格式一：格式一：35for i:=1 to n do for j:=1 to m do for k:=0 to j do fi,j:=max
18、(fi,j,fi-1,j-k+ai,k);格式二：格式二：36【问题描述问题描述】 假设你想以最美观的方式布置花店的橱窗。你有假设你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一束花，每束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从并从左至右，从1至至V顺序编号，顺序编号，V是花瓶的数目，编号为是花瓶的数目，编号为1的花瓶在最左边，编号的花瓶在最左边，编号为为V的花瓶在最右边。花束则可以移动，并且每束花用的花瓶在最右边。花束则可以移动，并且每束花用1至
19、至F的整数唯一标识。标识的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果花束的整数决定了花束在花瓶中排列的顺序，即如果Ij，则花束，则花束I必须放在花束必须放在花束j左左边的花瓶中。边的花瓶中。 例如，假设杜鹃花的标识数为例如，假设杜鹃花的标识数为1，秋海棠的标识数为，秋海棠的标识数为2，康乃馨的标识数为，康乃馨的标识数为3，所，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左边的花瓶中，如果花瓶的数目大于花束的数目，的花瓶中，秋海棠必须入在康乃馨
20、左边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。则多余的花瓶必须空置，每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表示。示。、花店橱窗布置（、花店橱
21、窗布置（IOIIOI9999）37花花 瓶瓶12345花花 束束1、杜、杜鹃鹃花花723-5-24162、秋海棠、秋海棠521-410233、康乃馨、康乃馨-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都可以接受，但你只需输出其中一种摆放方式。假设条件（Asumption）1F100，其中F为花束的数量，花束编号从1至F。FV100，其中V是花瓶的数量。-50Aij50，其中Aij 是花束i在花瓶j
22、中时的美学值。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
23、、秋海棠、秋海棠521-410233、康乃馨、康乃馨-215-4-2020ai,jai,j fi,jfi,j 方法一方法一40分析：分析：ai,jai,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不放入第不
24、放入第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+fi,i=a1,1+a2,2+ai,i;+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,
25、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
26、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:
27、=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 for j:=i to m-(n-im-(n-i) do) do begin begin fi,jfi,j:=min;:=min; for k:=i-1 to
28、j-1 do for k:=i-1 to j-1 do if fi-1,k if fi-1,kfi,jfi,j then then begin begin fi,jfi,j:=fi-1,k; :=fi-1,k; pathi,jpathi,j:=k; end;:=k; end; inc(fi,j,ai,jinc(fi,j,ai,j);); end; end; ansans:=min;:=min; for i:=n to m do for i:=n to m do if if fn,ifn,iansans then then begin begin ansans:=:=fn,ifn,i; last
29、:=i; end; last:=i; end;46dfs(n,lastdfs(n,last) ) procedure procedure dfs(i,j:longintdfs(i,j:longint);); begin begin if if pathi,jpathi,j0 then0 then begin begin dfs(i-1,pathi,j); dfs(i-1,pathi,j); write(jwrite(j, );, ); end end else else write(jwrite(j, );, ); end; end;47你刚刚继承了首珍贵的、没有发行的歌曲，它们由流行的演唱组
30、录制。你的计划是选择其中一些歌曲来发行个唱片，每个唱片至多包含分钟的音乐，唱片中的歌曲之间不能重复。由于你是一个古典音乐的爱好者，所以你没办法区分这些歌曲的价值，你按照下面的标准作选择： 1) 这些唱片中的歌曲必须按它们写作的顺序排序。（如果第一个唱片录制了歌曲、，则第二个唱片只能从开始选择） 2)包含歌曲的总数量尽可能的多。输入：第一行包含数值，（不大于的整数），下面包含首歌曲的长度，它们按写作的顺序排列，没有一首歌曲超出唱片的长度，而且不可能将所有歌曲都放在唱片中。输出：输出应是按照标准进行选择个唱片，所能包含的最多歌曲数目。样例：输入：5 6 44 3 4 4 5输出：43 3、制作唱片
31、、制作唱片48用用aiai保存第保存第i i首歌曲的长度。首歌曲的长度。si,jsi,j 用用1 1张盘可以保存张盘可以保存i i到到j j首歌曲之间最多的歌曲数目。首歌曲之间最多的歌曲数目。设设fi,jfi,j=前前i i首歌用首歌用j j张盘可以录制的最多数量。张盘可以录制的最多数量。状态转移方程：状态转移方程：fi,jfi,j=maxfk-1,j-1+sk,i =maxfk-1,j-1+sk,i (j=k=i)(j=k=i) 一部分是用一部分是用j-1j-1张盘把前张盘把前k-1k-1首歌能录制的最大数量，另一部首歌能录制的最大数量，另一部分是用一张盘在第分是用一张盘在第k k到第到第i
32、 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 read
33、ln(n,v,mreadln(n,v,m);); for i:=1 to n do for i:=1 to n do read(airead(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 wh
34、ile ajajbkbk do / do /插入排序插入排序i i到到j j的歌曲的歌曲 begin bk+1:=begin bk+1:=bkbk; sumk+1:=; sumk+1:=sumk+ajsumk+aj; ; dec(k);enddec(k);end; ; bk+1:= bk+1:=ajaj; sumk+1:=; sumk+1:=sumk+ajsumk+aj; if sumnum+1=v then if sumnum+1=v then inc(numinc(num); ); si,jsi,j:=num; :=num; end; end; end; end;51时间：时间：O(N3+
35、N2*M)空间：空间：N*Mfi,jfi,j 与第与第j-1j-1列有关列有关52XXXXXXXXXXXXXXXXXXXX1 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,
36、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分钟分钟未使用。可以录制的歌曲的最大数量。未使用。可以录制的歌曲的最大数量。55for i:=1 to n do for j:=0 to m do for k:=0 to t do begin fi,j,k:=
37、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)，在装船时，按照传送带传送货物的
38、顺序向船上搬运货物，由于传动带在传送过程中始终不停止，并且速度很快，一旦错过不选某件货物，就无法再搬到船上，如：第条船装了货物a1,a3，则第条船只能从a开始装，即a2被错过，无法再被装船。而且装船的规则是，只有一条船装完后才能装下一条船。没有一件货物的重量超过船的载重量。编程：选择哪货物装到船上使这条船所能装载货物的最大重量（某件货物要么装要么不装）。输入：第一行：，m，w第二行：a1,a2,an输出：条船所能运载货物的最大重量。样例：样例：输入：输入：210输出：输出：（选择（选择 8 4 5）7 7、集装箱运输、集装箱运输58提示： 求货物的最大载重量，而不是求最多能装多少件货物！59算
39、法一：算法一：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,w60for 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,
40、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条船的最大载重量。
41、条船的最大载重量。 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;求求
42、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)668 8、最大、最大mm子段和问题子段和问题给定由n个整数（可能为负整数）组成的序列a1,a2,.an，以及一个正整数m，要求确定序列a1,a2,.an的m个不相交子段，使这m个子段的总合达到最大。输入：第一行：N，m。n=1000,m=10 第二行：a1,a2,.an。中间一个空格。ai
43、=(-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=a
44、1f1=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,jdi,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; fo
45、r j:=i+1 to n do for j:=i+1 to n do begin begin sum:= sum:=fmax(sum+aj,ajfmax(sum+aj,aj);); max:= max:=fmax(max,sumfmax(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:=-maxlongi
46、nt; 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
47、=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）72f1,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
48、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;ansans:=-:=-maxlongintmaxlongint; ;for i:=m to n do for i:=m to n do ansans:=:=fmax(ans,fi,mfmax(ans,fi,m)
49、;);时间：时间：O（N2*M）73有一个由数字0, 1，2，. ，9组成的数字串（长度不超过200），问如何将M(0=M=20)个加号(“+”)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。输入格式数字串在输入文件的第一行行首（数字串中间无空格且不折行），的值在输入文件的第二行行首。输出格式所求得的最小和的精确值。输入输出举例输 入 ：82363983742 3输 出：2
50、170 9 9、最小加法表达式、最小加法表达式74分析：分析：S:string; 输入的数串。输入的数串。n=length(s);m=加号的个数；加号的个数；设：设：fi,j=在数串在数串s的前个字符中插个加号所得的最小值。的前个字符中插个加号所得的最小值。目标：目标：fn,m状态转移方程：状态转移方程： fi,j=minfk,j-1+dk+1,i (j=k=i-1) di,j=数串数串s中第到第个字符组成的数值。中第到第个字符组成的数值。前个字符中插个加号所得的最小值由两部分组成：一部分前个字前个字符中插个加号所得的最小值由两部分组成：一部分前个字符加符加j-1个加号形成的最小值，另一部分第
51、个加号形成的最小值，另一部分第k+1到第到第i字符作为一个数。字符作为一个数。 j=k1) do while (di,j,k=0)and(k1) do dec(kdec(k);); di,j,0:=k; di,j,0:=k; end; end; end; end;78大小比较大小比较 function function fmin(a,b:data):datafmin(a,b:data):data; ; varvar i:integer; i:integer; begin begin if a0b0 then exit(b); if a0b0 then exit(b); if a0b0 then
52、 exit(a); if a00 do while i0 do begin begin if aibi then exit(b); if aibi then exit(b); if aibi then exit(a); if ai if b0lenlen then then lenlen:=b0;:=b0; for i:=1 to for i:=1 to lenlen do ci:=ai+bi; do ci:=ai+bi; for i:=1 to for i:=1 to lenlen do do begin begin ci+1:=ci+1+ci div 10; ci+1:=ci+1+ci d
53、iv 10; ci:=ci mod 10; ci:=ci mod 10; end; end; if clen+10 then if clen+10 then inc(leninc(len);); c0:= c0:=lenlen; ; faddfadd:=c;:=c; end; end;80设设: :fi,j:fi,j:合并第合并第i i到到j j堆的最小得分。堆的最小得分。datai,j:datai,j:第第i i到到j j堆石子的总数量。堆石子的总数量。 则则:datai,j:=ai+ai+1+:datai,j:=ai+ai+1+aj+aj动态转移方程动态转移方程: :fi,j=min(fi
54、,k+fk+1,j)+datai,jfi,j=min(fi,k+fk+1,j)+datai,j i=k=j-1 i=k=j-1初始值：初始值：fi,i=0;fi,i=0;目标：目标：f1,nf1,n1010、石子合并、石子合并( (线性线性) )81数据范围的估计：数据范围的估计：DataI,j: DataI,j: 最大最大20*100=200020*100=2000，integerinteger。FI,j: FI,j: 最大估计：需要最大估计：需要2*n-12*n-1次合并，每次合并后的最大值不次合并，每次合并后的最大值不超过超过20002000。N=100N=100 （2*100-12*1
55、00-1）* *2000=400000,longint2000=400000,longint即可。即可。82求求datai,jdatai,j for i:=1 to n dofor i:=1 to n do begin begin datai,i:=ai; datai,i:=ai; for j:=i+1 to n do for j:=i+1 to n do datai,j:=datai,j-1+aj; datai,j:=datai,j-1+aj; end; end;时间复杂度: n283 for i:=1 to n do fi,i:=0; for i:=1 to n do fi,i:=0;初始
56、化初始化 for p:=1 to n-1 do for p:=1 to n-1 do 枚举阶段：距离枚举阶段：距离p=j-ip=j-i for i:=1 to n-p do for i:=1 to n-p do 枚举状态：枚举状态：ii begin begin j:=i+p; j:=i+p; fi,j:= fi,j:=maxlongintmaxlongint; ; for k:=i to j-1 do for k:=i to j-1 do 枚举决策枚举决策 fi,j:=min(fi,j,fi,k+fk+1,j); fi,j:=min(fi,j,fi,k+fk+1,j); fi,j:=fi,j+
57、datai,j; fi,j:=fi,j+datai,j; end; end;时间时间:O(N3)动规求解过程：动规求解过程：84Datai,jDatai,j 方法方法2 2：for i:=1 to n do read(ai);for i:=1 to n do read(ai);for i:=2 to n dofor i:=2 to n do aiai:=ai-1+ai;:=ai-1+ai;Datai,j:=aj-ai-1Datai,j:=aj-ai-1fi,j=min(fi,k+fk+1,j)+fi,j=min(fi,k+fk+1,j)+aj-ai-1aj-ai-1 i=k=j-1 i=k=j
58、-185环形石子合并环形石子合并样例样例2 2：4 44 5 9 44 5 9 486环变成线性环变成线性: :长度长度: 2n-1: 2n-1a1,a2.an,an+1.a2n-1; a1,a2.an,an+1.a2n-1; an+i=aian+i=aifi,j:fi,j:合并合并i i到到j j堆的最小得分。堆的最小得分。ai:1ai:1到到i i堆石子的总数量。堆石子的总数量。初始值：初始值：fi,i=0;fi,i=0;fi,j=minfi,k+fk+1,j+aj-ai-1 . fi,j=minfi,k+fk+1,j+aj-ai-1 . (i=k=j-1) (i=k=j-1)目标：目标：
59、ansans=minf1,n,f2,n+1,.,fn,2n-1=minf1,n,f2,n+1,.,fn,2n-1time O(n3)time O(n3)87其它方法？ans=minf1,n,f2,1,f3,2,.,fi,i-1,.,fn,n-1;88最高加分设fi,j:中序遍历结果序列为i.j的最大加分； i=j 枚举根结点k：i=k=j，得到不同的二叉树:左子树中序遍历结果是: i,k-1,最大加分为:fi,k-1.右子树中序遍历结果是: k+1,j,最大加分为:fk+1,j.方程： fi,j=maxfi,k-1*fk+1,j+ak; （i=k=j）初始化： fi,i=ai； 其它？目标：f
60、1,n1111、加分二叉树、加分二叉树(noip2003)(noip2003)89输出先序遍历序列：输出先序遍历序列：任意中序遍历结果任意中序遍历结果ij中，一旦确定其根结点中，一旦确定其根结点k，二，二叉树就唯一确定了。叉树就唯一确定了。在求在求fi，j的同时，记下的同时，记下ij的根的根k，用，用rootI,j=k。求得了所有的求得了所有的rootI,j后，递归调用后，递归调用root1,n即可输即可输出。出。90 for i:=1 to n+1 do fi+1,i:=1; for i:=1 to n do fi,i:=ai; for p:=1 to n-1 do for i:=1 to
61、n-p do begin j:=i+p; for k:=i to j do 枚举根接点 if fi,jfi,k-1*fk+1,j+ak then begin fi,j:=fi,k-1*fk+1,j+ak; rooti,j:=k; end; end;动规过程动规过程91 输出先序遍历结果输出先序遍历结果procedure preorder(i,j:integer);中序结果为ij begin if i=j then begin write(rooti,j, ); 输出根结点 preorder(i,rooti,j-1); 先序遍历左子树 preorder(rooti,j+1,j); 先序遍历右子树
62、 end; end;调用：preorder(1,n);92设A和B是两个字符串。我们可以通过下面的三种字符操将字符串转换为字符串。字符操作包括：（）：删除A中的一个字符。（）：在A中插入一个字符。（）：将A中一个字符改为另一个字符。对于给定的字符串和，要求用最少的操作步骤将转换为。输入：第一行：，第二行：。输出：将转换为所用的最少步数。样例：输入：acdefabcde输出:21212、字符串转换、字符串转换93分析：设fi,j=将的前个字符变成的前个字符的最少操作数。A=acdef B=abcdei=length(A); j=length(B)从后向前依次比较分析，fi,j分三种情况：1)删除
63、A中的最后一个字符：问题变为A中剩下的i-1个字符和B中的个字符的转换。即：fi,jFi-1,j+12)在A的最后插入一个字符：插入后使ai+1=bj,问题变为A中的前i个字符和B中的前j-1个字符的转换。即：fi,jfi,j-1+13)将A中的一个字符改为另一个字符。如果ai=bj,则fi,jfi-1,j-1 如果aibj,将ai换成bj;则fi,jfi-1,j-1+194综上所述：设fi,j=将的前个字符变成的前个字符的最少操作数 fi,jminfi-1,j+1; fi,j-1+1; fi-1,j-1,(ai=bj); fi-1,j-1+1,(aibj)假设：N=length(a);M=l
64、ength(b);初始条件：fi,0=i; 0=i=n：删除A中的i字符使A变成B； f0,j=j; 0=j=m：在A中插入j个字符使A变成B ；目标：fn,m95readln(sa); readln(sb);la:=length(sa); lb:=length(sb);for i:=0 to maxn do begin fi,0:=i;f0,i:=i; end;for i:=1 to la do for j:=1 to lb do if sai=sbj then fi,j:=fi-1,j-1 else fi,j:=min(fi-1,j-1,fi,j-1,fi-1,j)+1;writeln(fla,lb);96
