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

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

信息学竞赛常用算法思想

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

正如在例3 - 5中所看到的,程序1 5 - 1做了一些不必要的工作。为了避免f (i,y)的重复计算,必须定义一个用于保留已被计算出的f (i,y)值的表格L,该表格的元素是三元组(i,y,f (i,y) )。在计算每一个f (i,y)之前,应检查表L中是否已包含一个三元组(i,y, * ),其中*表示任意值。如果已包含,则从该表中取出f (i,y)的值,否则,对f (i,y)进行计算并将计算所得的三元组(i,y,f (i,y) )加入表L。L既可以用散列(见7 . 4节)的形式存储,也可用二叉搜索树(见11章)的形式存储。

2. 权为整数的迭代方法

当权为整数时,可设计一个相当简单的算法(见程序1 5 - 2)来求解f ( 1 ,c)。该算法基于例3 - 4所给出的策略,因此每个f (i,y) 只计算一次。程序1 5 - 2用二维数组f [ ][ ]来保存各f 的值。而回溯函数Tr a c e b a c k用于确定由程序1 5 - 2所产生的xi 值。函数K n a p s a c k的复杂性为( n c),而Tr a c e b a c k的复杂性为( n )。

程序15-2 f 和x 的迭代计算

template<class T>

void Knapsack(T p[], int w[], int c, int n, T** f)

{// 对于所有i和y计算f [ i ] [ y ]

// 初始化f [ n ] [ ]

for (int y = 0; y <= yMax; y++)

f[n][y] = 0;

for (int y = w[n]; y <= c; y++)

f[n][y] = p[n];

// 计算剩下的f

for (int i = n - 1; i > 1; i--) {

for (int y = 0; y <= yMax; y++)

f[i][y] = f[i+1][y];

for (int y = w[i]; y <= c; y++)

}

f[1][c] = f[2][c];

if (c >= w[1])

}

{// 计算else {x[i] = 1;

c -= w[i];}

x[n] = (f[n][c]) ? 1 : 0;

}

3. 元组方法( 选读)

程序1 5 - 2有两个缺点:1) 要求权为整数;2) 当背包容量c 很大时,程序1 5 - 2的速度慢于程序1 5 - 1。一般情况下,若c>2n,程序1 5 - 2的复杂性为 (n2n )。可利用元组的方法来克服上述两个缺点。在元组方法中,对于每个i,f (i, y) 都以数对(y, f (i, y)) 的形式按y的递增次序存储于表P(i)中。同时,由于f (i, y) 是y 的非递减函数,因此P(i) 中各数对(y, f (i, y)) 也是按f (i, y)

上一页第3页

你可能喜欢

  • 算法设计
  • 计算机算法
  • 信息学竞赛
  • 动态规划算法
  • 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