1 / 81
文档名称:

动态规划的分类解析.ppt

格式:ppt   大小:407KB   页数:81页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

动态规划的分类解析.ppt

上传人:hh思密达 2022/5/14 文件大小:407 KB

下载得到文件列表

动态规划的分类解析.ppt

文档介绍

文档介绍:动态规划
动态规划
什么是动态规划
动态规划的条件
动态规划的关键
几种常见动态规划的种类
例题分析
什么是动态规划
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
但是经分解得到的子问题往往不是相互塔问题,于是可以借助动态规划高效解决。
状态的确定
我们用opt[i][j]表示从左上角入口移动到第i行j列的最小代价。
则opt[i,j]=min{opt[i-1][j], opt[i][j-1]) + a[i][j];
最终输出opt[n][n];
代码
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf(“%d”, &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <=n; j++)
f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];
printf(“%d\n”, f[n][n]);
乘积最大
国际数学联盟确定的“2000—世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛活动,你的好挚友XZ也有幸得以参与。活动中,主持人给全部参与活动的选手出了这样一道题目:
设有一个长度为N(N≤40)的数字串,要求选手运用M(M≤6)个乘号将它分成M+1个部分,找出一种分法,使得这M+1个部分的乘积最大。
同时,为了帮助选手能够理解题意,主持人还举了如下一个例子:
有一个数字串:312,当N=3,M=1时会有两种分法:
⑴3×12=36
⑵31×2=62
这时,符合题目要求的结果是:31×2=62。现在,请你帮助你的好挚友XZ设计一个程序,求得正确的答案。
分析
由于自然数位数的上限为40,乘号数的上限为6,因此最大乘积位数的上限接近42位。明显,运算任何整数类型都无法容纳如此之大的数据,只能接受高精度运算,限于篇幅,对于高精度的加法运算、乘法运算和比较大小的运算,这里不作介绍,只是对的乘号最佳插入方式进行探讨:
假设s1‥si(2≤i≤n)中插入j个乘号,其中s1‥sk中插入了j-1个乘号,即乘式中的第j+1项为sk+1‥si(j≤k≤i-1):
分析

ans[i][j]——长度为i的数串中插入j个乘号的最大乘积(整型数组)。明显
ans[i][0]=s1..si对应的整型数组;
ans[i][j]=max{ans[k][j-1]×sk+1..si} (1≤i≤n, 1≤j≤min{i-1,m},j≤k≤i-1)
ans[n][m]即为其解。
分析
由于乘式中第j+1项sk+1‥si为常量,因此要使得ans[i][j]最大,则s1‥sk中插入j-1个乘号的乘积必需最大;同样,为了找寻第j个乘号的最佳插入位置,必需一一查阅子问题ans[j][j-1]‥ans[i-1][j-1]的解。明显该问题具备无后效性、最优子结构的特征,适用于动态规划方法。
状态的确定
我们用ans[i][j]表示前i个字符插入j个乘号可以获得的最大值
则有:
ans[i][0]=s1..si
ans[i][j] = max{ans[k][j-1]×sk+1..si} (j≤k≤i-1)
ans[n][m]即为其解。
代码
输入n,m和数串s;
for i←1 to n do ans[i][0]←s1..si对应的整数数组;
for i←2 to n do  
{阶段:枚举数串的长度}
for j←1 to min{i-1,m} do  
{状态:枚举长度为i的数串中插入的乘号个数}
for k←j to i-1 do
{决策:枚举第j个乘号的插入位置}
begin
next←sk+1..si对应的整数数组; {计算第j+1项}
ans[i][j]←max{ans[i][j], ans[k][j-1]×next};
{计算状态转移方程}
end;{for}
输出最大乘积ans[n][m];
过河
在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很厌烦踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点起先,不停的向终点方向跳动。一次跳动的距离是S到T之间的

最近更新

2023年辽宁省辽勤集团有限公司校园招聘考试题.. 3页

管理品牌之道模板 24页

一种出入境公文流转系统的分析与设计的中期报.. 3页

2023年注册土木工程师(水利水电)之专业基础知.. 10页

一株鸡传染性贫血病毒野毒株致病性及其全基因.. 2页

管理信息系统案例分析-系统分析 34页

管理体系内审员审核知识培训教程(Q) 26页

纺织品定制市场的需求分析 24页

管理会计(厦大版)A 27页

《诚斋诗话》研究的中期报告 2页

北师大版语文第六册《送往小木屋的信》ppt课件.. 31页

北师大版语文四年级上册《走月亮》教学设计 27页

算法导论Let3-GrowthofFu 23页

北师大版八年级语文上册第课《小石潭记》教案.. 18页

北师大版二年级语文上册《绒毛小熊》flash教学.. 27页

2023初三暑假学习计划15篇 29页

简单酿造红葡萄酒的方法 23页

2022年江西省文化和旅游系统事业单位人员招聘.. 3页

2022年体育知识竞赛试题400题及答案 5页

北京版六年级上册《顶碗少年》PPT课件 27页

包覆机岗位培训教材 27页

办公室安全生产管理职责 27页

初二上《落日的幻觉》教案 35页

刍议水利工程中影响粉喷桩施工质量的因素及其.. 27页

竟选客服主管演讲稿 23页

2023小学义务教育质量监测存在问题的整改方案.. 9页

2023年江苏吉尔多肽杯化学竞赛试题WORD版有答.. 15页

鱼类学检索表(水产动物营养与饲料学鱼类学重点.. 3页

落脏腹针庁法 14页

新课程标准(2011) 2页