文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 信息学竞赛常用的算法思想讲座之一(动态规划)
侵权投诉

信息学竞赛常用的算法思想讲座之一(动态规划)

信息学竞赛常用算法思想

中华IT学习网doc.guandang.net 官方总站:圣才学习网doc.guandang.net

优子序列构成的结论,可得到f 的递归式。f ( 1 ,c) 是初始时背包问题的最优解。可使用( 1 5 - 2)式通过递归或迭代来求解f ( 1 ,c)。从f (n, * )开始迭式, f (n, * )由(1 5 - 1)式得出,然后由( 1 5 - 2)式递归计算f (i,*) ( i=n- 1,n- 2,., 2 ),最后由( 1 5 - 2)式得出f ( 1 ,c)。

对于例1 5 - 2,若0≤y<1 0,则f ( 3 ,y) = 0;若y≥1 0,f ( 3 ,y) = 1 5。利用递归式(1 5 - 2),可得f (2, y) = 0 ( 0≤y<10 );f(2,y)= 1 5(1 0≤y<1 4);f(2,y)= 1 8(1 4≤y<2 4)和f(2,y)= 3 3(y≥2 4)。因此最优解f ( 1 , 11 6 ) = m a x {f(2,11 6),f(2,11 6 - w1)+ p1} = m a x {f(2,11 6),f(2,1 6)+ 2 0 } = m a x { 3 3,3 8 } = 3 8。

现在计算xi 值,步骤如下:若f ( 1 ,c) =f ( 2 ,c),则x1 = 0,否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解,用f (2, c-w1) 表示最优解。依此类推,可得到所有的xi (i= 1.n) 值。

在该例中,可得出f ( 2 , 11 6 ) = 3 3≠f ( 1 , 11 6 ),所以x1 = 1。接着利用返回值3 8 -计算x2 及x3,此时r = 11 6 -w1 = 1 6,又由f ( 2 , 1 6 ) = 1 8,得f ( 3 , 1 6 ) = 1 41 6 ),因此x2 = 1,此时r= 1 6 -w2 = 2,所以f (3,2) =0,即得x3 = 0。

动态规划方法采用最优原则( principle of optimalityt r a c e b a c k)以构造最优解。

算问题时,复杂性将急剧下降。这时很自然地避免了重复计算。比避免重复计算的递归程序更快。

3.2 应用

3.2.1 0/1背包问题

1. 递归策略

在例3 - 4 1 5 - 2)的一个很自然的方法便是使用程序1 5 - 1p、w 和n 为输入,且p 为整型,F(1,c) 返回f ( 1 ,c) 值。

程序15-1

{// 返回程序1 5 - 1的时间复杂性t (n)满足:t ( 1 ) =a;t(n)≤2t(n- 1)+b(n>1),其中a、b 为常数。通过求解可得t (n) =O( 2n)。

例3-5 设n= 5,p= [ 6 , 3 , 5 , 4 , 6 ],w=[2,2,6,5,4] 且c= 1 0 ,求f ( 1 , 1 0 )。为了确定f ( 1 , 1 0 ),调用函数F ( 1 , 1 0 )。递归调用的关系如图1 5 - 1的树型结构所示。每个节点用y值来标记。对于第j层的节点有i=j,因此根节点表示F ( 1 , 1 0 ),而它有左孩子和右孩子,分别对应F ( 2 , 1 0 )和F ( 2 , 8 )。总共执行了2 8次递归调用。但我们注意到,其中可能含有重复前面工作的节点,如f ( 3 , 8 )计算过两次,相同情况的还有f ( 4 , 8 )、f ( 4 , 6 )、f ( 4 , 2 )、f ( 5 , 8 )、f ( 5 , 6 )、f ( 5 , 3 )、f (5,2) 和f ( 5 , 1 )。如果保留以前的计算结果,则可将节点数减至1 9,因为可以丢弃图中的阴影节点。

上一页第2页

你可能喜欢

  • 算法设计
  • 计算机算法
  • 信息学竞赛
  • 动态规划算法
  • c语言常用算法

热门文档

相关文档

  • 动态规划讲座

    第6讲 动态规划专题讲座 35页 1财富值 acm系列讲座-动态规划 39页 免费 信息学竞赛常用的算法思想... 19页 10财富值 石少俭算法讲座1动态规划 49页 1财富...

  • 算法合集之《浅谈贪心思想在动态规划中的应用》

    动态规划是信息学竞赛中的两种常用算法,本文着重讨论了贪心的思想是如何巧妙的...-1- 2006 年全国信息学冬令营讲座 下文就贪心思想如何解决动态规划面临着的这...

  • 常用算法大全-动态规划算法

    信息学竞赛常用的算法思想... 19页 10财富值 常用算法(八)——动态规划......动态规划是本书介绍的五种算法设计方法中难度最大的一种,它建立在最优原则的...

  • 动态规划讲座

    第6讲 动态规划专题讲座 35页 1财富值 acm系列讲座-动态规划 39页 免费 信息学竞赛常用的算法思想... 19页 10财富值喜欢此文档的还喜欢 第二节 动态规划 4...

  • 信息学竞赛常用算法

    信息学竞赛常用算法!!! 算法大全 一、数论算法 1....(1,n); } 思路三:可使用动态规划求解 USACO1.2...G.基数排序 思想:对每个元素按从低位到高位对每一...

  • 算法合集之《浅谈数形结合思想在信息学竞赛中的应用》

    算法合集之《浅谈数形结合思想在信息学竞赛中的...动态规划解题...9 小结......赛中的项链,使用 Raney 引理都是最简单的方法之一。2 用几何图形辅助思考...

  • 算法合集之《浅谈贪心思想在动态规划中的应用》

    【关键字】 贪心法,动态规划,状态,时间复杂度【摘要】贪心法和动态规划是信息学竞赛中的两种常用算法,本文着重讨论了贪心的思想是如何巧妙的运用到动态规划的解题...

  • 部分贪心算法思想在信息学竞赛中的应用

    部分贪心 【正文】 正文】 引言 贪心在信息学竞赛中,是一种非常重要的思想。 ...状态的决策中采用搜索或者动态规划这类可以保证正确性的算法来处理, 而对于第 2...

  • 动态规划算法_百度百科

    是信息学竞赛中选手必须熟练掌握的一种算法,他以其...编辑本段 基本思想动态规划算法通常用于求解具有某种...编辑本段 作用在编程中常用解决最长公共子序列问题...

  • 动态规划算法1

    各类信息学竞赛的重要考察内容。 ? 不同于其他算法...? 初学者不易掌握其思想,需要做大量的题。 ? ...动态规划的常见模型及例题 4 引例1:数字三角形【...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email