noip教程--动态规划的优化.pptVIP

  1. 1、本文档共43页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
动态规划的优化方法 YALI 朱全民 动态规划优化的内涵 动态规划算法的时间复杂度= 阶段数*每个阶段状态转移的状态数 *每次状态转移的时间 或者:状态总数*每次状态转移的时间 重点:减少每个阶段的状态数,也就是减少了状态总数 优化方法1:改进状态的表示 例1:理想收入问题 理想收入是指在股票交易中,以1元为本金可能获得的最高收入,并且在理想收入中允许有非整数股票买卖。 已知股票在第i天每股价格是V[i]元,1≤i≤M,求M天后的理想收入。 方法一 设F[i]表示在第i天收盘时能达到的最高收入,则有F[i]的递推关系式: 方法二 设P[i]表示前i天能获得的最多股票数,则可列出状态转移方程: 设Q[i]表示前i天能达到的最大收入,则可列出状态转移方程: 方法三 分析:上述公式的含义是当0=ji 时,求Q[i-1]和Q[j]*v[i]/v[j]的最大值 对于0=ji,要求Q[i],实际上Q[1]…Q[i-1]都已经求出,因此我们只要搞一个变量保存Q[j]/V[j] 的最大值即可,记为MaxQ. 这样,公式可以写成 优化方法2: 利用决策的单调性 例3:最长上升序列问题 f(i)=max{f(j)+1} (1=ji=n, bjbi) 上式含义为:对于所有的1=ji,bjbi,必须找一个最大的f(j) 反过来说,对于1=ji,必须找到一个最大的f(j),满足bjbi。 分析 对方程进行一下改进:对于 ji, f[i] = max{f(j)+1}, 其中,min{j | r [j]a[i]} r[j]为所有等于f[j]时a[j]的最小值。 因此,我们可以搞一个队列维护f(j)的上升序列。 对于当前的i,利用二分查找在队列查找到满足条件bjbi的f(j) 用bi去替换与f(i)相等的bj 若bj=bi,则舍弃bi 若bjbi,则用bi替换bj 若在对尾,则直接插入 显然该算法的时间复杂度为O(n*log(n)) 方法3:根据最优解的性质减少决策 例5:石子合并问题 猜想 合并第i堆到第j堆石子的最优断开位置s[i,j]要么等于i,要么等于j-1,也就是说最优合并方案只可能是: { (i) (i+1… j) } 或 { (i… j-1) (j) } 证明: 设合并第i堆到第j堆石子的最优断开位置 s[i,j]=p,且ipj-1。 情况1:t[i, p]≤t[p+1,j] 由于ip,所以可以设q=s[i,p]。于是最优合并方案为: { [ (i…q) (q+1...p) ] (p+1…j) } ,它的得分, F1=m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+t[i, p] 我们可以构造如下的合并方案: { (i…q) [ (q+1...p) (p+1…j) ] },它的得分, F2 = m[i, q]+m[q+1,p]+m[p+1,j]+t[i, j]+t[q+1,j] 由于qp,所以t[i, p]≤t[p+1,j]t[q+1,j],所以F1F2。 这与合并第i堆到第j堆石子的最优断开位置 s[i, j]=p矛盾 情况2:t[i, p]t[p+1,j] 与情况1是对称的。 方法4:利用贪心思想减少状态总数 例6:快餐问题 Peter最近在R市开了一家快餐店,为了招揽顾客,该快餐店准备推出一种套餐,该套餐由A个汉堡,B个薯条和C个饮料组成。价格便宜。为了提高产量,Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡,薯条和饮料,由于每条生产线每天所能提供的生产时间是有限的、不同的,而汉堡,薯条和饮料的单位生产时间又不同。这使得Peter很为难,不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序,计算一天中套餐的最大生产量。为简单起见,假设汉堡、薯条和饮料的日产量不超过100个。 输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡,薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10),第四行为N个不超过10000的正整数,分别为各条生产流水线每天提供的生产时间,中间以一个空格分开。 输出:每天套餐的最大产量。 分析 设p[i,j,k]表示前i条生产线生产j个汉堡,k个薯条的情况下最多可生产饮料的个数。 用r[i,j,k]表示第i条生产线生产j个汉堡,k个薯条的情况下最多可生产饮料的个数。 状态转移方程如下: p[i,j,k] = Max{p[i-1,j1,k1]+r[i,j-j1,k-k1]} 约束条件: ( 0=

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档