- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
石头合并问题的动规讨论
动态规划设计: 阶段i:石子的每一次合并过程,先两两合并,再三三合并,...最后N 堆合并 状态s:每一阶段中各个不同合并方法的石子合并总得分。 决策:把当前阶段的合并方法细分成前一阶段已计算出的方法,选择其中的最优方案 以 dp[i][j] 来表示 从i开始合并j个元素,dp[i,j] 表示 dp[i][j] 的最优解。 举例:9,7,6,9,20 dp[1][1] 表示 第一个元素和它自己合并 dp[1,1] = 0 dp[1][2] 表示 第一个元素 和他后面的一个元素合并 即 9,7合并 dp[1,2] = 16 dp[1,1] 到 dp[5,5] 的取值如下: 我们需要的是dp[1,5],dp[i][5],dp[5,5]的最小值。 可以得到最优解113 代码 运行结果: 谢谢 石头合并问题的动规讨论 内容描述: 在一个圆形操场的四周摆放着n 堆石子。现 将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。(因为最大与最小的寻找方式相同,在此只讨论寻找最小得分) 解决方案: 贪心算法: 以数据 9 6 7 9 20 为例 贪心的合并过程: 1、9 13 9 20 //6与7合并 score = 13 2、22 9 20 //9与13合并 score =22 3、22 29 //9与20合并 score = 29 4、51 //24,29合并 score = 51 总分: 13+22+29+51 = 115 动规合并过程:序列: 9 6 7 9 20 1、15 7 9 20 //9,6合并 score = 15 2、15 16 20 //7,9合并 score = 16 3、31 20 //15,16合并 score = 31 4、51 //31,20合并 score =50 得分 15+16+31+51= 113 分析: 因为贪心算法是一只寻找局部最优解,不能保证全局最优解,因此贪心算法不可取 动规讨论 ? 最优解结构的探讨:假设有 i,i+1,i+2,i+3,i+4,…,i+j 个石头堆合并。 则有合并方式 [ (i) (i+1,i+2,i+3,...,i+j) ] [ (i,i+1) (i+2,i+3,...i+j) ] [ (i,i+1,i+2) (i+3,...i+j) ] . . . [ (i,i+1,...,i+j-1) (i+j) ] 以G[i,j]表示从i 合并到j的得分, 则 G[i,j] == G[i,k]+G[k+1][j] + total(i,j) 其中total(i,j)为最后一次合并的得分 为石子的总数 而 G[i,k] , G[k+1][j]的总得分 ,也用上式求出
您可能关注的文档
最近下载
- 【Renesas】CAN入门书.pdf
- 页岩砖项目可行性研究报告.docx
- 公路建设安全管理台帐(参考)用表格模板6182.pdf
- 2024-2030年中国捡石机行业市场发展趋势与前景展望战略分析报告.docx
- 高中英语教学课件:教学课件Unit 3 Environmental Protection Project.pptx
- (高清版)B-T 3836.1-2021 爆炸性环境 第1部分:设备 通用要求.pdf VIP
- 车位进行特许权经营服务投标方案(技术方案).pdf
- 基于5G通信的智能移动终端设计与实现.docx VIP
- 数智化赋能高校“一站式”学生社区建设.docx VIP
- 推进高校“一站式”学生社区建设.docx VIP
文档评论(0)