动态规划2概述ppt课件.ppt

《动态规划2概述ppt课件.ppt》由会员分享，可在线阅读，更多相关《动态规划2概述ppt课件.ppt（79页珍藏版）》请在三一办公上搜索。

1、动态规划,什么是动态规划？,（一）动态规划是解决多阶段决策问题的一种方法。,多阶段决策问题,对于整个问题，可以根据其时间或其他顺序分成若干个前后相关联的子问题，问题的全局最优包含其子问题的局部最优，即满足最优子结构性质，并且无后效性，有边界条件，且一般划分为很明显的阶段，存在一条或多条状态转移方程。,“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决策子序列。包含有非局部最优的决策子序列，一定不是最优决策序列。,最优性原理,如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能

2、从左往右走），使得所经过的权值和除以4的余数最小。,MOD 4余数最小问题,设所有点从左至右编号为14，MIN（i）表示前I个点的最优值，很容易得出一个方程：Min(i)=min(Min(I-1)+numI-1,1)mod 4,Min(I-1)+numI-1,2)mod 4 通过这个方程可以求出一条路径为（2+3+1）MOD 4=2但最优值实际上是（2+1+1）MOD 4=0。为什么会出错呢？,分析,观察以上数据发现取Min()的时候，动态规划求出来的最优值为，而正确的值应该为0，由此可知本题对应于一条最优路径，并不是这条路径上的所有点的最优值都是从点到该点可得的最优值，对于每一个阶段都取最优

3、值并不能保证求出最优解，即不满足最优化原理，因此这种规划方法在本题行不通。,让我们来换一个思路思考本题，因为本题是要求总和除以余数最小的一条路径，我们先撇开最小余数不去管它，而是将本题改为从点1到点的所有路径中，求出每条路上权值和除以的不同余数的个数。我们设一个数组canI,j表示从点1至点可不可以求出一条路径是该路径的权值总和除以的余数为，那么又可以得出一个方程：canI,j:=canI-1,k and(k+numI,p)mod 4=j)(0=k=3,1=p=2)can1,0=true can1,1=false can1,2=false can1,3=false 通过这个方程我们可以求出从点

4、1至点可以达到的所有余数，我们只要从这些余数中选出一个值最小的输出就行。,动态规划的指导思想是：在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因为有些问题不符合最优性原理。,两种算法的差别在于，贪心法产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的。而动态规划会产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列。,什么是

5、动态规划？,（二）动态规划实际上就是一种排除重复计算的算法，更具体的说，动态规划就是用空间换取时间。,问题：给定一个具有N层的数字三角形如下图，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最大路径得分。,7 3 88 1 0 2 7 4 4 4 5 2 6 5,初看此题不难想到本题可以用递归算法来解决：Function Max(I,J:integer):longint;从当前位置开始的可得的最优值Var s1,s2:Longint;记录从左右斜线向下走的可达的最优值Begin If(In)Or(JI)Then Max:=-1 当前位置不存在，最

6、优值为-1 Else Begin S1:=Max(I+1,j)+triangleI,j;沿左斜线向下走 S2:=Max(I+1,j+1)+triangleI,j;沿右斜线向下走 If s1s2 then Max:=s1 Else max:=s2;选取最优走法 End;End;由以上算法不难算出其时间复杂度为2n，而本题N最大为100，显然当N比较大时是无法在规定时间内出解的，但本题又很难找出理想的剪枝方法。,通过以下搜索树可以看出在求Max(2,1),Max(2,2)的时候两次调用函数Max(3,2)，也就是说，函数Max(3,2)被重复计算了两次，其实在这棵搜索树中有很多结点都被重复计算了多

7、次，程序时效显然就会大打折扣了，实际上这也是搜索之所以会效率低下的一大原因。既然知道了上述搜索算法效率低的原因。对于同一个函数值搜索多次是没有必要的，因此我们可以每求出一个函数的值便可将其用数组保存下来，到了下次要用的时候直接从数组里调出来用就可以了。这样时间复杂度一下子降成了O(N*N)函数个数最多不超过N*N个。,Function Max(I,J:integer):longint;从当前位置开始的可得的最优值Var s1,s2:Longint;记录从左右斜线向下走的可达的最优值Begin If AI,j-1 Then Begin 函数I，J已求出，直接赋值即可 Max:=AI,j;Exit

8、;End;If(In)Or(JI)Then Max:=0 当前位置不存在，最优值为0 Else Begin S1:=Max(I+1,j)+triangleI,j;沿左斜线向下走S2:=Max(I+1,j+1)+triangleI,j;沿右斜线向下走 If s1s2 then AI,j:=s1 Else AI,j:=s2;选取最优走法 Max:=AI,j;记录该函数值End;End;,动态规划问题具有以下基本特征：1、问题具有多阶段决策的特征。2、每一阶段都有相应的“状态”与之对应，描述状态的量称为“状态变量”。3、每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态。4、每一阶段的

9、最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。,动态规划的基本模型,阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。决策：根据题意要求，对每个阶段所做出的某种选择性操作。状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。,动态规划的几个概念,动态规划问题的一般解题步骤,1、判断问题是否具有最优子结构性质，若不具备则不能用动态规划。2、把问题分成若干个子问题（分阶段）。3、建立状态转移方程（递推公式）。4、找出边界条件。5、将已知边界值带

10、入方程。6、递推求解。,线性规划模型,例1：机器分配问题。总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M=150，N=100。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个N*M的矩阵，表明了第I个公司分配J台机器的盈利。,分析,用机器数来做状态，数组FI，J表示前I个公司分配J台机器的最大盈利。则状态转移方程为:FI，J=MaxFI-1，K+ValueI，

11、J-K(1=I=N,1=J=M,0=K=J)初始值:F(0,0)=0时间复杂度O(N*M2),最长不下降序列,设有整数序列b1,b2,b3,bm，若存在下标i1i2i3 in，且bi1bi2bi3 bin，则称 b1,b2,b3,bm中有长度为n的不下降序列bi1,bi2,bi3,bin。求序列b1,b2,b3,bm中所有长度(n)最大不下降子序列输入：整数序列。输出：最大长度n和所有长度为n的序列个数。,分析,（1）设f(i)为前i个数中的最大不下降序列长度,则f(i)=maxf(j)+1(1=ji=m,bjbi)边界为F(1)=1(2)设t(i)为前i个数中最长不下降序列的个数,则t(i)

12、=t(j)(1=ji=m,bjbi,f(i)=f(j)-1)初始为t(i)=1当f(i)=n时，将t(i)累加举例：1 2 3 4 6 5 8 10 9 f:1 2 3 4 5 5 6 7 7 t:1 1 1 1 1 1 2 2 2答案：f=7时，边界为t=4,进一步,(3)求本质不同的最长不下降序列个数有多少个？如：1 2 3 4 6 5 8 10 9 有，1 2 3 4 6 8 10,1 2 3 4 5 8 10,1 2 3 4 6 8 9,1 2 3 4 5 8 9 都是本质不同的。但对于 1 2 2 3 3 5 4 f 1 2 2 3 3 4 4 t 1 1 1 2 2 4 4 答案有

13、8个，其中4个1 2 3 5，4个1 2 3 4,改进算法,上例显然对于相两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中的i个数在原序列中的位置。可见，求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时，便不累加t(j)。这样就避免了重复。上述算法的时间复杂度为O(n2),进一步,(3)求本质不同的最长上升序列个数有多少个？如：1 2 3 4 6 5 8 10 9 有，1 2 3 4 6 8 10,1 2 3 4 5 8 10,1 2 3 4 6 8

14、 9,1 2 3 4 5 8 9 都是本质不同的。但对于 1 2 2 3 3 5 4 f 1 2 2 3 3 4 4 t 1 1 1 2 2 4 4 答案有8个，其中4个1 2 3 5，4个1 2 3 4,改进算法,上例显然对于两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中第i个数在原序列中的位置。可见，求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时，便不累加t(j)。这样就避免了重复。上述算法的时间复杂度为O(n2),有一条河从东向西将某地区分

15、为南北2个部分。河的两岸各有N个城市。北岸的每个城市都与南岸的某个城市是友好城市，而且关系是一一对应的。现在要求在2个友好城市之间建立一条航线，但由于天气的缘故，所有的航线都不能相交，因此，就不能给所有的友好城市建立友好航线。请设计一个修建航线的方案，能建最多的航线而且不相交。输入：第一行为一个正整数N(N=1000)以下N行，记第i行有一个正整数j，表示北岸的城市i与南岸的城市j互为友好城市。其中城市编号是按从东到西排列的。输出：仅一行，即最多的航线数。,船(ceoi),首先我们需要判定对于给定的两条航线是否相交，设北岸城市i1，j1(i1 j1)分别与南岸城市i2，j2互为友好城市，那么这

16、两条航线不相交(以下简称为i1，j1相容)的充要条件是I2=J2。(结论1)由下图就可以很容易地得到这个结论。,北岸：,南岸：,图 一,图 二,分析,从上面的结论可以看出，最优的选择方案中，如果将所有航线按北岸村庄号从小到大排序，序列中每一个北岸村庄对应的南岸村庄号必然满足B1B2B3Bn（n为选出来的航线数）。同样，对于任一个方案，如果北岸村庄排好序后，与之对应的南岸村庄也是按升序排列，那么该方案必然不存在相交的两条航线；相反，如果南岸村庄不是按升序排列，必存在两条相交的航线。因此，我们可以先将各航线按北岸村庄号排一个序，那么最优的方案必然是从相对应的南岸村庄中找出一个最长不下降序列，该序列

17、的长度即为问题的解。,凸多边形三角划分,给定一个具有N（N50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？输入文件：第一行 顶点数N 第二行 N个顶点（从1到N）的权值输出格式：最小的和的值 各三角形组成的方式输入示例：5122 123 245 231 输出示例：The minimum is：12214884 The formation of 3 triangle:3 4 5,1 5 3,1 2 3,分析,设FI,J（IJ）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到

18、下面的动态转移方程：FI,J=MinFI,K+FK,J+SI*SJ*SK(0IKJ=N)初始条件:F1，2=0目标状态:F1,N但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算,在数字串中插入若干(K个)乘号使总的乘积最大。分析：定义 从 l 到 r 加入 k 个乘号的最大乘积值为p(l,r,k)。p(l,r,k)=max d(l,q)*p(q+1,r,k-1),数字最大乘积,解题思路 定义:从 l 到 r 加入 k 个乘号的最大乘积值p(l,r,k)。p(l,r,k)=max d(l,q)*p(q+1,r,k-1),树形动态规划(皇宫看守),太平

19、王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。数据输入：输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树，描述如下：第1行 n，表示树中结点的数目。第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0i=n），在该宫殿安置侍卫所需

20、的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，.，rm。对于一个n（0 n=1500）个结点的树，结点标号在1到n之间，且标号不重复。数据输出：输出到OUTPUT.TXT文件中。输出文件仅包含一个数，为所求的最少的经费。,输入数据示例,输出数据示例 25,问题分析,求给定的带权树的符合下面条件的子顶点集合V：1 若点iV，则所有与i相邻的点j可被标号。2 任意一个点j，若j不属于V，则j可被标号。3 S=（Weighti，iV），并且S最小。,考虑到树本身的特性：除了根节点外，每一个节点都仅与该节点的父节点与儿子节点有关系；大多数情况下，每个节点的状况都是由

21、它的儿子节点的状况决定的。这与动态规划的无后效性要求相符，再加上本题求的又是最优方案，这一切都与动态规划算法不谋而合。,要求覆盖以节点i为顶点的树的最佳方案Vi，显然只需考虑节点i属于或不属于集合V两种情况，两者择优即可。即Vi=minVi1，Vi2选与不选（1表示属于，2表示不属于）,(一）若iV，则对于i的任一儿子j，也只有属于或不属于集合V两种情况：（1）若jV，则问题转化到求Vj1的小一级规模问题，转化成功；(2)若j不属于V，则要不求Vj2，要不就是j不能被j的任意一个儿子标号，则求所有Vk（k为j的儿子），Vi1求好了。,（二）若i不属于V，i一定要能被i的某个儿子j标号，这时求所

22、有Vj（j为i的儿子）。若所有的j都是j被j的儿子标号时最“省”（即所有Vj=Vj2），那么实际上按这样的方案没有一个jV,造成了i不能被标号。这时只要找一个牺牲最小的i的儿子j，把方案Vj2换成Vj1。这样就求出了覆盖以节点i为顶点且不包括节点i的最佳节点集Vi2。,状态转移方程,通过上面的分析，我们很容易得到下面这组状态转移方程：F(i)=minF(i,1),F(i,2)选或者不选F(i,1)=Weight(i)+minF(j),minF(k,1),F(k,2)选，i点以下最小花费=i花+min i儿子，min孙子选不选F(i,2)=F(j)；若所有F(j)F(j,1)，则换取代价最小的F

23、(j,2)（以上j为i儿子，k为j儿子）边界条件F(i)=F(i,1)F(i,1)=Weight(i)F(i,2)=+（以上i为叶子节点）,动态规划模型的建立,1、一般动态规划 某些问题在状态的选择上会遇到一些困难，我们可以采用一种类似于枚举的动态规划。,例题1：骨牌游戏,一张骨牌可被分为两个正方形。每个正方形为空或有1至6个点。如下图上面的一排正方形点数总和为6+1+1+1=9，底下一排的点数为1+5+3+2=11。上部和底部之差为2。任一张骨牌能被转动180，保持其正面始终朝上。为了使骨牌上下点数之差最少，求所需旋转的次数最少为多少？例如上图，至多只需将最后一张骨牌旋转一次，便能使差值为0

24、，因此在此情况下，答案为1。,分析,我们不妨先不考虑最少旋转次数，而是找出一个使上下两行绝对值差最小的方案。也许有人会想到用FI表示前I张骨牌能够成的最小差值，构造一个动态规划方程来解决该问题。但只要细想就会发现，该问题用这种方式规划不满足最优性原理，用这种形式的动态规划实际上是一种贪心，有反例！注意到骨牌上的点数范围很小，只可取0到6，因此，我们可以用FI，J表示前I张骨牌能否构造出上下差为J的方案。于是我们可以列出如下动态转移方程：fI,j=fI 1,j(aI bI)or fI 1,j(bI-aI)其中AI、BI分别表示第I张骨牌最初上下两面的点数。对应的两种转移方式则分别表示第I张骨牌翻

25、动与第I张骨牌不翻动的情况。边界：f0,0=True 至于最后求出的最少差值，只要从Fn，j中寻找一个可以取到的绝对最小的J即可。由于n最大为1000，骨牌上的点数为0到6，所以最小差值的范围也只是-6000到6000，该算法在最坏的情况下要计算1000*12000次，时间效率比起搜索，要快很多。,现在的问题是如何求出最少翻动的骨牌数。受到前面方程的启发，我们可以重新定义一下F数组，用FI，J表示前I张骨牌构成差值J要 翻动的最小骨牌数。类似的，我们可以列出如下方程：fI,j=minfI 1,j(aI bI),fI 1,j(bI aI)+1 由于第一种选择不翻动第I张骨牌，所以最小翻动次数在原

26、基础上不变。而第二种选择要翻动骨牌I，所以最小翻动次数要加1。边界：f0,0=0 初始化：将整个F数组的值都附成一个足够大的数MAX，不难想到，如果用前I张骨牌不可构成差值J，最后FI，J的值一定为MAX。要求出最小差值和最小翻动次数，只要从FN，J中选出一个不为max，且绝对值最小的J，选出的J对应的FI，J的值即为问题的解。注意：因为问题的处理涉及到绝对值，所以如果FI，J与FI，-J的情况都有可能取到，我们应该从这两个量中选出一个小的作为最小翻动骨牌数。,小优化,假设前I-1张骨牌可以翻出的最小差值为min，可以翻出的最大差值为max。注意，这个最小差值与问题中描述的不同，它是上面一行的

27、和减去下面一行的和，而不是上面一行的和减去下面一行和的绝对值。易知，前I张骨牌能够翻出的最小差值不会小于min-abs(aI bI)，最大差值不会大于max+abs(aI bI)，利用这一规律，在求FI，J的值时，我们可以将J循环的起始值和终值设为min和max。min和max的值也在计算过程中不断更新。这样可以减少一些不必要的计算，提高程序的效率。,动态规划模型的建立,2、多次动态规划 有些问题的求解过程对应多个状态转移方程；或者虽对应一个状态转移方程，但由于内存空间限制，一次动态规划仅能计算出最有解的值，无法构造最有解的形成过程。在这种情况下，需要进行多次动态规划。,最长公共子串问题,有两

28、个字符串A，B，当存在一个严格递增的整数序列i1，i2，im，满足a1=bi1，a2=bi2，am=bim，我们则说A包含于B。例如，“adg”包含于“abcdefg”，而不包含于“gfedcba”。现在有三个字符串A，B，C，要求你找出一个满足以下条件的最长的字符串D。D包含于A；D包含于B；D包含于C。输入：A，B，C。输出：D。,分析,首先，定义一个字串“前缀”的概念：给定一个字串s=s1sm。对于I=0.m，定义s的第I个前缀为sI=s1si。三个输入串A，B，C的所有前缀组成了最长公共子串的子问题空间。由此，我们发现最长公共子串的最优子结构性质。设：A=a1，am；B=b1，bn；C

29、=c1，ch。A，B，C的最长公共子串为D=d1，dk，D的长度为k。,性质1：am=bn=ch，则dk=am=bn=ch且dk-1是am-1，bn-1，ch-1的一个最长公共子串。性质2：ambn，amch，bn=ch，则dkam，蕴含D是am-1和B、C的一个最长公共子串。,性质3：bnam，bnch，am=ch，则dkbn，蕴含D是bn-1和A、C的一个最长公共子串。性质4：cham，chbn，am=bn，则dkch，蕴含D是ch-1和A、B的一个最长公共子串。,由此可见，字串A、B和C的最长公共字串包含了三个字串前缀的最长公共字串，说明该问题具备最优子结构的性质。,设fI，j，k为ai

30、，bj，ck的一个最长公共子串的长度（0im，0jn，0kh）。fm，n，h为问题的解，则状态转移方程为：当（j=0）or（k=0）时，fI，j，k=0；当（ai=bj=ck）时，fI，j，k=fI-1，j-1，k-1+1；当（aibj）或（bjck）时，fI，j，k=maxfI-1，j，k，fI，j-1，k，fI，j，k-1。,由于A，B，C三个字串的长度上限为10000，空间耗费较大,为此：（1）采用指针类型：fIj，k；（2）及时收回内存：由于计算fI时，只需要fI-1，因此可及时释放内存空间。,（3）进行两次动态程序设计：由于f1fI-2已释放，无法根据状态转移方程构造完整的最长公共子

31、串，因此必须进行两次动态规划：第一次动态方程设计，根据frfm构造aram中所含的最长公共子串。第二次动态程序设计，根据f1fI-2构造a1ar-1中所含的最长公共子串，并与第一次动态规划产生的公共子串拼接，形成完整的公共子串D。,双层动态规划,农 田 个 数(count.pas)你的老家在河北农村。过年时，你回老家去拜年。你家有一片NM农田，将其看成一个NM的方格矩阵，有些方格是一片水域。你的农村伯伯听说你是学计算机的，给你出了一道题：他问你：这片农田总共包含了多少个不存在水域的正方形农田。两个正方形农田不同必须至少包含下面的两个条件中的一条：边长不相等左上角的方格不是同一方格,输入 输入数

32、据第一行为两个由空格分开的正整数N、M（1=mn=1000）第2行到第N+1行每行有M个数字（0或1），描述了这一片农田。0表示这个方格为水域，否则为农田（注意：数字之间没有空格，而且每行不会出现空格）输出 满足条件的正方形农田个数。样例输入 样例输出 3 3 5 110 110 000,分析,(1)设FI，J表示以方格（I，J）为右下角，可以得到的最大无水正方形边长，那么显然如果（I，J）是水域，FI，J=0；否则FI，J=MinFI-1，J，FI，J-1，FI-1，J-1+1(2)求出了F数组的值后，我们可以用F1I表示F数组中，值为I的个数。(3)显然，假定边长为I的正方形数目为SumI

33、，那么有SumI=SumI+1+F1I(4)最后只要算出Sum数组各个值的和为问题的解。,动态规划时间效率的优化,一、减少状态总数1、改进状态表示状态的规模与状态表示的方法密切相关，通过改进状态表示减小状态总数是应用较为普遍的一种方法。,有一批编号为1至N且尺寸规格一样的箱子。现在要将其中某些箱子叠放起来，使叠放的高度最大，箱子叠放的规则如下：一、每个箱子上最多只能直接叠放一个箱子；二、编号较小的箱子不能放在编号较大的箱子之上；决定不会产生后效性三、每个箱子都给出了自身重量与可承受重量，每个箱子上的所有箱子重量之和不得超过该箱的可承受重量。输入箱子数N（1N1000）及每个箱子的自身重量与可承

34、受重量，两个数值均为小于等于3000的正整数。输出最多可叠放的箱子总数M和每个箱子的编号。,例题3：叠放箱子,箱子是按编号顺序叠放，所以可用动态规划求解。设：WeightI表示第I个箱子的重量。SupportI表示第I个箱子的承受重量。F(i,j)表示前i个箱子中最多可选出F(i,j)个叠放，还可承受重量j。线性的划分 F(i,j)=Max F(i-1,j-Weighti)+1,F(i-1,j)。放，不放（其中，J=supportI）,算法分析,上述算法的状态总数为O(n*Total_Weight)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)。总时间复杂度=1000*3000

35、=3*106,改进一下状态的表示方式，设FI，j表示前i个箱子叠放j个箱子时可承受的最小重量。Fi，j：=MinFi-1，j，Fi-1，j-1+Weighti Ans：=Max（J|Fi，j）（Fi，j=supporti）上述算法的状态总数为O(n*n)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)，所以总的时间复杂度=1000*1000=1*106。,算法优化,改进后的算法的时间复杂度是改进前的1/3。但如果在Tot-Weight的值很小，而n的值相当大，前面一种方法更好。对于不同的题目，要从多方面分析，选择适合的最优方法。,2、选择适当的规划方向 规划方向的选择主要有两种：

36、顺推和逆推。若初始状态确定，目标状态不确定，则应考虑采用顺推，反之，若目标状态确定，而初始状态不确定，就应该考虑采用逆推。那么，若是初始状态和目标状态都已确定，可以选用双向规划。,动态规划时间效率的优化,双向规划与双向搜索的主要思想类似：在状态空间十分庞大，而初始状态和目标状态又都已确定，为了减少状态的规模，分别从初始状态和目标状态两个方向进行扩展，并在两者的交汇处得到问题的解。,例题4：Divide(Merc2000)有价值分别为1.6的大理石各a1.6块，现要将它们分成两部分，使得两部分价值和相等，问是否可以实现。其中大理石的总数不超过20000。,动态规划时间效率的优化,令S=(i*ai

37、)，若S为奇数，则不可能实现，否则令Mid=S/2，问题转化为能否从给定的数中中选取部分数，使其和为Mid。设mi,j表示能否从价值为1.i的大理石中选出部分大理石，使其价值和为j，若能，则用true表示，否则用false表示。则状态转移方程为：mi,j=mi,j OR mi-1,j-i*k(0kai)规划的边界条件为：mi,0=true；0i6若mi,Mid=true，0i6，则可以实现题目要求，否则不可能实现。,算法分析,上述算法每个状态转移的状态数为ai，每次状态转移的时间为O(1)，状态总数是所有值为true的状态的总数。,本题在i较小时，值为true的状态也较少，但随着i的增大，值为

38、true的状态也急剧增多，影响了算法的时间效率。我们分别求出从价值为1.3的大理石中选出部分大理石所能获得的所有价值和，和从价值为4.6的大理石中选出部分大理石所能获得的所有价值和。再判断是否存在和为Mid的价值和，从而得出问题的解。,算法优化,状态转移方程改进为：当i3时：mi,j=mi,j OR mi-1,j-i*k(1kai)当i3时：mi,j=mi,j OR mi+1,j-i*k(1kai)规划的边界条件为：mi,0=true；0i7 1到3 4到6 若存在k，使得m3,k=true,m4,Mid-k=true，则可以实现题目要求，否则无法实现。,回顾本题的优化过程可以发现：本题的实际

39、背景与双向搜索的背景十分相似，同样有庞大的状态空间，有确定的初始状态和目标状态，状态量都迅速增长，而且可以实现交汇的判断。从本题的优化过程，我们认识到，双向扩展以减少状态量的方法不仅适用于搜索，同样适用于动态规划。这种在不同解题方法中，寻找共通的属性，从而借用相同的优化思想，可以使我们不断创造出新的方法。,动态规划时间效率的优化,二、减少每个状态转移的状态数 在使用动态规划方法解题时，对当前状态的计算都是进行一些决策并引用相应的已经计算过的状态，这个过程称为“状态转移”。因此，每个状态可能转移的状态数是决定动态规划算法时间复杂度的一个重要因素。,动态规划时间效率的优化,1、决策量的优化 分析问

40、题最优解的性质，缩小决策集合，也可以减少每个状态可能转移的状态数。NOI96中的添加号问题，是从“所得的和最小”这一原则出发，仅在等分点的附近添加号，从而大大减少了每个状态转移的状态数，降低了算法的时间复杂度。,动态规划时间效率的优化,添加号问题,有一个由数字1，2，.，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式

41、的值133。输入格式从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），的值在输入文件的第二行行首。输出格式在屏幕上输出所求得的最小和的精确值。,在一个操场上摆放着一排n（n20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。,例题5：石子归并区间模型,设n堆石子依次编号为1，2，.，n。各堆石子数为d1.n，则动态规划的状态表示为：mi,j，1ijn，表示合并di.j所得到的最大得分，则状态转移方程和边界条件为：mi,j=0 i=j,算法分析,ij,该算法的时间复杂度为O(n3)。,令si,j=k，表示合并的断开位置，可以发现：si,j要么等于i+1，要么等于j。,于是，状态转移方程优化为：mi,j=0 i=j MI，J=MAXMI，J-1，MI+1，J）+ij 优化后每个状态转移的状态数减少为O(1)，算法总的时间复杂度也降为O(n2)。,