- 1、本文档共31页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
* 3、以自底向上的方式计算出最优值 void KnapSack(int v[],int w[],int c,int n,int m[][11]) { int jMax=min(w[n]-1,c); for (j=0;j=jMax;j++) m[n][j]=0; for (j=w[n];j=c;j++) m[n][j]=v[n]; for (i=n-1;i1;i--) { int jMax=min(w[i]-1,c); for (j=0;j=jMax;j++) m[i][j]=m[i+1][j]; for (j=w[i];j=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } * * 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 (1)最优子结构性质 (2)重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息,构造最优解。 动态规划(DP)Dynamic Programming * 动态规划法的定义:在求解问题中,对于每一步决策,列出各种可能的局部解,再依据某种判定条件,舍弃那些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一步都是最优解来保证全局是最优解。 4.1算法总体思想 动态规划通常应用于最优化问题,即做出一组选择以达到一个最优解。关键是存储子问题的每一个解,以备它重复出现。 * 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。 4.1算法总体思想 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。 * [问题4-1]:存在一个数字三角形,从顶到底有多条路径, 每一步可沿左斜线向下或垂直向下。路径所经过的数字之和称为路径得分,要求求出最小路径得分。 状态表示1-1 用一元组D(X)描述问题,D(X)表示从顶到达第X层的得分。但是一元组D(X)描述的子问题不能满足最优子结构性质,因为D(X)的最优解可能不包含子问题D(X-I)的最优解。这样,动态规划方法是无法在状态表示1-1上应用。 动态规划对状态表示的要求 * 状态表示 1-2 用二元组D(X,Y)描述问题,D(X,Y)表示到达第X层第Y个位置时的得分,那么 D(X,Y)的最优解包含了子问题D(X+1,Y)或D(X+1,Y-1)的最优解,状态转移方程为 : D(X,Y)= min{D(X+1,Y),D(X+1,Y-1)}+A[X,Y] D(4,*)= A[4,*] * D(i,j) 1 2 3 4 5 6 7 8 1 6 7 2 5 6 6 8 3 6 3 4 5 5 3 4 3 8 1 2 3 8 1 2 D(X,Y)= min {D(X+1,Y),D(X+1,Y-1)} + A[X,Y] * 声明部分; 输入a数组,M行N列;//下标从1开始 for (j = 1; j = N; j++) //O(N) D[M][j]=a[M][j]; for (i = M-1; i =1; i--) //自底向上DP { for (j =M-i+1,n=1; n=2*i; j++,n++) D[i][j]=min(D[i+1][j],D[i+1,j-1])+a[i][j]; } coutmin(D[1]); //输出第一行最小值 } * D(i,j) 1 2 3 4 5 6 7 8 1 1 1 2 3 4 3 4 3 6 5 6 6 6 4 9 13 6 8 9 7 D(X,Y)= min {D(X-1,Y),D(X-1,Y+1)} + A[X,Y] * 4.1算法总体思想 动态规划设计一般要经历以下几个步骤: 1、划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。 2、确定状态:将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。 3、确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态,所以如果确定了决策,状态转移方程也就可以写出。 4、寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。 5、程
您可能关注的文档
- 施工现场管理细则解读.doc
- 汽包锅炉水汽监督课件解读.ppt
- 施工现场检查评分记录表(10张规范)_secret解读.doc
- 2013年中级职称财务管理考试题型含试题分析.doc
- 交通安全作用大——讲解.ppt
- 汽车4S店客户满意度实战中的应用技巧解读.ppt
- 汽车4S店市场部年度总结及下一年计划解读.ppt
- 机械原理大作业-凸轮结构20解读.doc
- 交通工程施工方案讲解.docx
- 交通护栏作用大永鑫护栏提醒您不要故意损毁讲解.ppt
- 广播电视播音员主持人全真模拟模拟题附答案详解(预热题).docx
- 危险化学品安全作业题库检测试题打印附参考答案详解【夺分金卷】.docx
- 教师资格考前冲刺练习试题含答案详解【夺分金卷】.docx
- 广播电视播音员主持人全真模拟模拟题(典型题)附答案详解.docx
- 教师资格考试综合练习附完整答案详解【精选题】.docx
- 人教版四年级下册数学期末测试卷1套.docx
- 2025广播电视播音员主持人自我提分评估完整版附答案详解.docx
- 2025年广播电视播音员主持人考试综合练习附答案详解【巩固】.docx
- 2025年教师资格能力提升B卷题库(夺冠)附答案详解.docx
- 2025年教师资格试卷及参考答案详解【满分必刷】.docx
文档评论(0)