程序设计方法-动态规划法

1、程序设计实践程序设计方法之动态规划1任务:摘桃子（1104)长满桃子的树很大，共有n层（最高层为第1层），第i层有i条树枝，树的形状呈一个三角形（如图）图中的点表示树枝，每个点上方的数字表示这条树枝最多能摘到的桃子数在摘得某枝条的桃子之后，小猴子只能选择往左上方爬或者是往右上方爬例如：摘了有6个桃子的树枝之后只能摘有2个桃子的树枝或是有3个桃子的树枝），然后继续摘桃子。小猴子现在想要从最低层开始一直爬到树顶（也就是最上面的那个枝条），摘尽可能多的桃子。请你编程帮他解决这个问题。1234652解题思路题目似曾相识？滑雪、迷宫可以用递归回溯方法解决建议自写递归回溯的代码3换一种思路从最低一层爬到最

2、顶点，经过的路径上数字之和最大A:1B:2C:3D:4E:6F:5第1阶段第2阶段第0阶段4思路先看第2阶段，到达顶点有2条路BA，可以摘到1个桃子，则经过B点到顶点最多摘得桃子数是：到达B点手中最多的桃子数+1CA，可以摘到1个桃子，则经过C点到顶点最多摘得桃子数是：到达C点手中最多的桃子数+1从上述两条路径中选择一条最优的令令P(X)表示从底层到X点可以摘到最多桃子数目，包含X点可以摘到的桃子数目则：P(A) = maxP(B)，P(C)+15思路（续）而第1阶段的P(B) = maxP(D), P(E)+2P(C) = maxP(E), P(F)+3按照题意，P(D),P(E),P(F)

3、分别初始化为4, 6, 5上述递推公式说明，要求P(A)需要先求出阶段1的P(B)和P(C)，而要得到P(B)和P(C)，需要知道P(D),P(E),P(F)6思路（续）显然，根据前面的递推过程求解，需要倒过来，从P(D),P(E),P(F)出发，先求出第1阶段的P(B)和P(C)，最后得到P(A)。7数据结构将长满桃子的树用二维数组保存数组行上存放桃树上一层中每个树枝上桃子数将节点上桃子数目存放在数组中只使用数组中对角线及下部分A:1B:2C:9D:7E:6F:5G:2H:3J:4I:68问题分析从二维数组最下面一行开始向上一行沿图中的直线前进，走到左上角的格子停止。行走路径上经过的格子中的

4、数字之和是猴子爬到树顶能拿到桃子的数目，我们定义为路径长度。原问题转化为求所有路径中路径长度的最大值。9问题分析（续）按照前面的思路，最长路径的长度是：P(A) = maxP(B), P(C)+1P(B) = maxP(D), P(E)+2P(C) = maxP(E), P(F)+9P(D) = maxP(G), P(H)+7P(E) = maxP(H), P(I)+6P(F) = maxP(I), P(J)+5P(G) = 2, P(H) = 3, P(I) = 6, P(J) = 4将底层到每个点的最长路径P也存放在二维数组中ABCDEFGHJIyx10数据结构(续)#define MAX

5、LAYER 3int peachtreeMAXLAYERMAXLAYER = 1, -1, -1, -1, 2, 9, -1, -1, 7, 6, 5, -1,2, 3, 6, 4 ;int PMAXLAYERMAXLAYER原问题转化为即求P03Px y = maxPx y-1, Px+1y-1+peachtreexyy 0, x + y = MAXLAYPER注意边界条件，Px 0 = peachtreex011最多能摘到22个桃子，路径如上图红色箭头所示yx12参考程序如下#include #include #include using namespace std;#define MAX

6、LAYER 110int maxnum(int x, int y)/返回2个整数中的大者if (x y)return x;elsereturn y;13参考程序（续）int main()int peachtreeMAXLAYERMAXLAYER;int PMAXLAYERMAXLAYER;int i, j, k, n;/读入数据cin n;k = 1;/当前这层的节点数目for (i = 0; i n; i+)/ n-i层的的节点for (j = 0; j peachtreejn-i-1;k+;14参考程序（续）/初始化Px0for (i = 0; i n; i+)Pi0 = peachtre

7、ei0;/递推过程Pxy = maxPxy-1, Px+1y-1+peachtreexyfor (j = 1; j n; j+)/ i是行号，j是列号for (i = 0 ; i + j n; i+)Pij = maxnum(Pij-1, Pi+1j-1)+peachtreeij;cout P0n-1 endl;return 0;15动态规划阶段状态决策状态转移方程16动态规划的几个概念:阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。决策：根据题意要求，对每个阶段所做出的某种选择性操作。状态

8、转移方程：用数学公式描述与阶段相关的状态间的演变规律。17动态规划相关概念动态规划是运筹学的一个重要分支，是解决多阶段决策过程最优化的一种方法所谓多阶段决策过程，是将所研究的过程划分为若干个相互联系的阶段，在求解时，对每一个阶段都要做出决策，前一个决策确定以后，常常会影响下一个阶段的决策。18动态规划相关概念（续）动态规划所依据的是“最优性原理”“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。最优决策序列的子序列，一定是局部最优决策子序列。包含有非局部最优的决策子序列，一定不是最优决策序列。19动态规划相关概念（续）动态规

9、划的指导思想是：在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因为有些问题不符合最优性原理。20动态规划与贪心法区别贪心法产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的。动态规划会产生许多判定序列，再按最优性原理对这些序列加以筛选，去除那些非局部最优的子序列。21 举例说明动态规划思路 问题： 在数字串中插入若干乘号使 总的乘积最大22 * * * s

10、 3 2 1 5 1 2 5 0 1 2 3 4 5 6 请插入3个乘号使乘积最大 32*15*12*5=28800 3*215*12*5=38700 321*51*2*5=16371023 解题思路 定义 : 从 l 到 r 加入 k 个乘号的最大乘积值 * p( l , r , k ) l l+1 l+2 . . . q q+1 q+2 . . . r d ( l , q ) p( q+1,r,k-1 ) d ( l , q )= slsl+1sq 24 p( l,r,k )=max d( l, q ) * p( q+1, r ,k-1 ) q=l,l+1,r-k q=l=0 3 2 1

11、5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,0)=3 p( q+1,r,k-1 )=p( 1,6,2 ) (p( 0,6,3)|q=0) = 3 * p( 1,6,2 ) 25 q=l+1=1 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,1)=32 p( q+1,r,k-1 )=p( 2,6,2 ) (p( 0,6,3)|q=1) = 32 * p( 2,6,2 )26 q=l+2=2 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,2)=321 p( q+1,r,k-1 )=p( 3,6,2 ) (p

12、( 0,6,3)|q=2) = 321 * p( 3,6,2 )27 q=l+3=3 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,3)=3215 p( q+1,r,k-1 )=p( 4,6,2 ) ( p( 0,6,3)|q=3) = 3215 * p( 4,6,2 )28p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 29p( 1,6,2 ) 2 1 5 1 2 5 2 * p(2,6,

13、1 ) 1 2 3 4 5 6 2 1 5 1 2 5 21 * p(3,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 215 * p(4,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 2151 * p(5,6,1) 1 2 3 4 5 6 30 p( 2,6,1 ) 1 5 1 2 5 1* 5125 2 3 4 5 6 1 5 1 2 5 15 * 125 2 3 4 5 6 1 5 1 2 5 15 1* 25 2 3 4 5 6 1 5 1 2 5 1512 *5 2 3 4 5 6 31 p(2,6,1) = max 1 * 5125 , 15 * 125 ,

14、 151 * 25 , 1512 * 5 = 7560 32 p( 3,6,1 ) 5 1 2 5 5 * 125 3 4 5 6 5 1 2 5 51 * 25 3 4 5 6 5 1 2 5 5 12* 5 3 4 5 6 p( 3,6,1 )=max5*125, 51*25, 512*5 = 2560 33 p( 4,6,1 ) 1 2 5 1 * 25 4 5 6 1 2 5 12 * 5 4 5 6 p( 4,6,1 ) = max 1 * 25, 12 * 5 = 6034 p( 5,6,1 ) 2 5 2 * 5 5 6 p(5,6,1) = 1035 p( 1,6,2 )= m

15、ax 2 * p( 2,6,1 ) , 21 * p( 3,6,1) , 215 * p( 4,6,1) , 2151 * p( 5,6,1) =max2*7560,21*2560,215*60,2151*10 = 53760 36 p( 2,6,2 ) 1 5 1 2 5 1* p(3,6,1 ) 2 3 4 5 6 1 5 1 2 5 15 * p(4,6,1) 2 3 4 5 6 1 5 1 2 5 151 * p(5,6,1) 2 3 4 5 6 p( 2,6,2 )= 1 * 2560, 15 * 60, 151 * 10 = 256037 p( 3,6,2 ) 5 1 2 5 5

16、* p(4,6,1 ) 3 4 5 6 5 1 2 5 51 * p(5,6,1) 3 4 5 6 p( 3,6,2 ) = 5 * 60 , 51 * 10 = 510 38 p( 4,6,2 ) 1 2 5 1 * 2 * 5 4 5 6 p( 4,6,2 ) = 1039 p( 4,6,2 ) 1 2 5 1* p(5,6,1 ) 4 5 6 p(5,6,1) = 2 * 5 = 10 p(4,6,2) = 1 * p(5,6,1) = 10 40p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3

17、,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6041p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6042p( 0,6,3)

18、= max 3 * 53760 , 32 * 2560 , 321* 510, 3215 * 60 = 163710 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 6043 P(l,r,k) k=0 k !=0 d(l,r) q=l q=l-k q=l+1 p(l+1,r,k-1) 求max值 d(l,l)* p(l+1,r,k-1) d(l,r-k)* p(r-k+1,r,k-1) p(r-k+1,r,k-1) p(l+2,r,k-1) d(l,l+1)* p(l+2,r,k-1) 44 dij j 0

19、1 2 3 4 5 6 i 0 3 32 321 3215 32151 321512 3215125 1 2 21 215 2151 21512 215125 2 1 15 151 1512 15125 3 5 51 512 5125 4 1 12 125 5 2 25 6 545 怎样计算这张表 ? di6, i=0,1,2,3,4,5,6. d06=s = 3215125 d16= 215125 = 3215125 % 1000000 = s % 1000000 s1=1000000 = s % s1 s1= s1/10 d26= d16 % s146 s1=1000000; d06=s;

20、 for( i=1; i=0; j- ) for( i=0; i= j; i + ) dij=dij+1/10; 48 参 考 程 序 #include / 预编译命令 #include / 预编译命令 using namespace std; / 使用名字空间 const int S=3215125; /定义常整数 int d77; /定义二维数组 49 int P( int l, int r, int k ) /计算P函数值 if ( k=0) return dlr; int x, ans=0; for( int q=1; qans ) ans=x; return ans; 50int m

21、ain() memset( d,0,sizeof(d); int s1,I,j; s1=1000000; d06=s; for( i=1; i=0; j- ) for( i=0; i= j; i + ) dij=dij+1/10; coutP( 0,6,3 )3 k=1 m=356 s(m,n)=min2*s(m,n-k)+s(m-1,k) k 1. s(m,n)=1, m=2, n=1 2. s(m,n)=1, m=3, n=1 3. s(m,n)=3, m=3, n=2 4. s(m,n)=3, m=4, n=2 5. s(m,n)=7, m=3, n=3 6. s(m,n)=5, m=4

22、, n=3 57 1 2 4 5 from temp1 temp2 to 358 分析 ： k值的选择是关键1. 问题的解决有若干个阶段，是一个多步 决策的过程。 2. 对于阶段 b 而言，阶段 a 的解决与之无关, 相关的只是阶段 a 解决后的状态。问题的 阶段划分满足无后效性的要求。3. 问题的最优策略是各阶段最优子策略的组 合，若问题 h 取得最优解，则其在阶段a, b, c 上也必然取得最优解。问题满足动态 规划的最优性原理。59 动态规划一般式 min s(m,n-k)+s(m-1,k)+s(m,n-k) k k=1,2,n m3 n1 s(m,n)= k=1 m=3 n1 1 m=

23、2 n=1 0 其它 60 m=3, n=2 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,2)=min 2*s(3,2-1)+s(3-1,1) =min 2*s(3,1)+s(2,1) =min 2*1 + 1 = 361 m=3, n=3 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,3)=min 2*s(3,3-1)+s(3-1,1) =min 2*s(3,2)+s(2,1) =min 2*3 + 1 = 762 m=3, n=4 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,4)=min 2*s(3,4-1)+s(3-1,1) =min 2*s(3,3)+s(2,1) =min 2*7 + 1 = 1563 m=3, n=5 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k)