欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    程序设计方法动态规划法.pptx

    • 资源ID:91065110       资源大小:306.90KB        全文页数:70页
    • 资源格式: PPTX        下载积分:11.9金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要11.9金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    程序设计方法动态规划法.pptx

    程序设计实践程序设计方法之动态规划任务:摘桃子(1104)长满桃子的树很大,共有n层(最高层为第1层),第i层有i条树枝,树的形状呈一个三角形(如图)图中的点表示树枝,每个点上方的数字表示这条树枝最多能摘到的桃子数在摘得某枝条的桃子之后,小猴子只能选择往左上方爬或者是往右上方爬例如:摘了有6个桃子的树枝之后只能摘有2个桃子的树枝或是有3个桃子的树枝),然后继续摘桃子。小猴子现在想要从最低层开始一直爬到树顶(也就是最上面的那个枝条),摘尽可能多的桃子。请你编程帮他解决这个问题。123465解题思路题目似曾相识?滑雪、迷宫可以用递归回溯方法解决建议自写递归回溯的代码换一种思路从最低一层爬到最顶点,经过的路径上数字之和最大A:1B:2C:3D:4E:6F:5第1阶段第2阶段第0阶段思路先看第2阶段,到达顶点有2条路BA,可以摘到1个桃子,则经过B点到顶点最多摘得桃子数是:到达B点手中最多的桃子数+1CA,可以摘到1个桃子,则经过C点到顶点最多摘得桃子数是:到达C点手中最多的桃子数+1从上述两条路径中选择一条最优的令令P(X)表示从底层到X点可以摘到最多桃子数目,包含X点可以摘到的桃子数目则:P(A)=maxP(B),P(C)+1思路(续)而第1阶段的P(B)=maxP(D),P(E)+2P(C)=maxP(E),P(F)+3按照题意,P(D),P(E),P(F)分别初始化为4,6,5上述递推公式说明,要求P(A)需要先求出阶段1的P(B)和P(C),而要得到P(B)和P(C),需要知道P(D),P(E),P(F)思路(续)显然,根据前面的递推过程求解,需要倒过来,从P(D),P(E),P(F)出发,先求出第1阶段的P(B)和P(C),最后得到P(A)。数据结构将长满桃子的树用二维数组保存数组行上存放桃树上一层中每个树枝上桃子数将节点上桃子数目存放在数组中只使用数组中对角线及下部分A:1B:2C:9D:7E:6F:5G:2H:3J:4I:61297652364问题分析从二维数组最下面一行开始向上一行沿图中的直线前进,走到左上角的格子停止。行走路径上经过的格子中的数字之和是猴子爬到树顶能拿到桃子的数目,我们定义为路径长度。原问题转化为求所有路径中路径长度的最大值。1297652364问题分析(续)按照前面的思路,最长路径的长度是: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也存放在二维数组中1297652364ABCDEFGHJIyx数据结构(续)#define MAXLAYER 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=peachtreex0最多能摘到22个桃子,路径如上图红色箭头所示1297652364yx参考程序如下#include#include#include using namespace std;#define MAXLAYER 110int maxnum(int x,int y)/返回返回2个整数中的大者个整数中的大者if(x y)return x;elsereturn y;参考程序(续)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+;参考程序(续)/初始化初始化Px0for(i=0;i n;i+)Pi0=peachtreei0;/递推过程递推过程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;动态规划阶段状态决策状态转移方程动态规划的几个概念动态规划的几个概念:阶段:据空间顺序或时间顺序对问题的求解阶段:据空间顺序或时间顺序对问题的求解划分阶段。划分阶段。状态:描述事物的性质,不同事物有不同的状态:描述事物的性质,不同事物有不同的性质,因而用不同的状态来刻画。对问题性质,因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。的求解状态的描述是分阶段的。决策:根据题意要求,对每个阶段所做出的决策:根据题意要求,对每个阶段所做出的某种选择性操作。某种选择性操作。状态转移方程:用数学公式描述与阶段相关状态转移方程:用数学公式描述与阶段相关的状态间的演变规律。的状态间的演变规律。动态规划相关概念动态规划是运筹学的一个重要分支,是解决多阶段决策过程最优化的一种方法所谓多阶段决策过程,是将所研究的过程划分为若干个相互联系的阶段,在求解时,对每一个阶段都要做出决策,前一个决策确定以后,常常会影响下一个阶段的决策。动态规划相关概念(续)动态规划所依据的是“最优性原理”“最优性原理”可陈述为:不论初始状态和第一步决策是什么,余下的决策相对于前一次决策所产生的新状态,构成一个最优决策序列。最优决策序列的子序列,一定是局部最优决策子序列。包含有非局部最优的决策子序列,一定不是最优决策序列。动态规划相关概念(续)动态规划的指导思想是:在做每一步决策时,列出各种可能的局部解,之后依据某种判定条件,舍弃那些肯定不能得到最优解的局部解。在每一步都经过筛选,以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝(从搜索角度看),效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优,不能保证全局最优,因为有些问题不符合最优性原理。动态规划与贪心法区别贪心法产生一个按贪心策略形成的判定序列,该序列不保证解是全局最优的。动态规划会产生许多判定序列,再按最优性原理对这些序列加以筛选,去除那些非局部最优的子序列。举例说明动态规划思路举例说明动态规划思路 问题:问题:在数字串中插入若干乘号使在数字串中插入若干乘号使 总的乘积最大总的乘积最大 *s 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=163710 解题思路 定义:从 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 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 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)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)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(0,6,3)|q=2)=321*p(3,6,2)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)p(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)2 1 5 1 2 5 2*p(2,6,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 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 p(2,6,1)=max 1*5125,15*125,151*25,1512*5 =7560 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 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 =60 p(5,6,1)2 5 2*5 5 6 p(5,6,1)=10 p(1,6,2)=max 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 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 =2560 p(3,6,2)5 1 2 5 5*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 p(4,6,2)1 2 5 1*2*5 4 5 6 p(4,6,2)=10 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 p(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)=60p(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)=60p(0,6,3)=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)=60 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)dij j 0 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 5 怎样计算这张表怎样计算这张表?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%s1 s1=1000000;d06=s;for(i=1;i=0;j-)for(i=0;i=j;i+)dij=dij+1/10;参参 考考 程程 序序#include /预编译命令预编译命令#include /预编译命令预编译命令 using namespace std;/使用名字空间使用名字空间 const int S=3215125;/定义常整数定义常整数 int d77;/定义二维数组定义二维数组 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;int main()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=3 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,n=3 1 2 4 5 from temp1 temp2 to 3 分析:k值的选择是关键1.问题的解决有若干个阶段,是一个多步问题的解决有若干个阶段,是一个多步 决策的过程。决策的过程。2.对于阶段对于阶段 b 而言,阶段而言,阶段 a 的解决与之无关的解决与之无关,相关的只是阶段相关的只是阶段 a 解决后的状态。问题的解决后的状态。问题的 阶段划分满足无后效性的要求。阶段划分满足无后效性的要求。3.问题的最优策略是各阶段最优子策略的组问题的最优策略是各阶段最优子策略的组 合,若问题合,若问题 h 取得最优解,则其在阶段取得最优解,则其在阶段a,b,c 上也必然取得最优解。问题满足动态上也必然取得最优解。问题满足动态 规划的最优性原理。规划的最优性原理。动态规划一般式动态规划一般式 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=2 n=1 0 其它其它 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 =3 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 =7 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 =15 m=3,n=5 k=1 s(m,n)=min 2*s(m,n-k)+s(m-1,k)s(3,5)=min 2*s(3,5-1)+s(3-1,1)=min 2*s(3,4)+s(2,1)=min 2*15+1 =31 m=3,n=6 k=1 s(m,n)=min 2*s(m,n-k)+s(m-1,k)s(3,6)=min 2*s(3,6-1)+s(3-1,1)=min 2*s(3,5)+s(2,1)=min 2*31+1 =63 m=4,n=3,k=1,2,3 s(m,n)=min 2*s(m,n-k)+s(m-1,k)s(4,3)=min 2*s(4,3-1)+s(4-1,1),2*s(4,3-2)+s(4-1,2),2*s(4,3-3)+s(4-1,3)=min 2*s(4,2)+s(3,1),2*s(4,1)+s(3,2),2*s(4,0)+s(3,3)=min 2*3+1,2*1+3,2*0+7 =5 m=4,n=4,k=1,2,3,4 s(m,n)=min 2*s(m,n-k)+s(m-1,k)s(4,4)=min 2*s(4,4-1)+s(4-1,1),2*s(4,4-2)+s(4-1,2),2*s(4,4-3)+s(4-1,3),2*s(4,4-4)+s(4-1,4)=min 2*s(4,3)+s(3,1),2*s(4,2)+s(3,2),2*s(4,1)+s(3,3),2*s(4,0)+s(3,4)=min 2*5+1,2*3+3,2*1+7,2*0+15 =9 s(4,5)=13,k=3 s(4,6)=17,k=3 s(4,7)=25,k=4 s(4,8)=33,k=4 s(4,9)=41,k=4 思路清楚了,请自己编出程序,思路清楚了,请自己编出程序,并运行通过。并运行通过。结结 束束

    注意事项

    本文(程序设计方法动态规划法.pptx)为本站会员(wuy****n92)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开