文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 部分贪心算法思想在信息学竞赛中的应用
侵权投诉

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

在某些数据规模非常大的问题当中,我们常常希望使用贪心法解决问题,但是纯粹的贪心在某些情形下会有反例存在。在这些情况下,我们可以采取一种折中的方案——部分贪心。降问题规模降低到较小的范围内以后,再采用其他方法解决。

中间的状态则采用贪心思想解决。这样平衡了算法的效率和正确性,得到了一个相对理想的结果,这种算法便是部分贪心算法。

举一个例子:求函数f(x) x2 sin(x )的最小值,从总体上来看,这个函数的取值主要和x2的取值有关,而sin(x )则起小规模干扰作用,但是如果单纯的取x2取最小值的位置却不能得到整个函数的最小值。事实上,取最小值的位置一定在x=0的附近位置。这样,我们贪心地得到了一个最小值x=0,然后在其附近采用枚举法取得真正的最小值。这便是部分贪心算法的一个形象化的例子。

部分贪心算法的优势

部分贪心在不影响算法总体复杂度的前提下,将边界上的特殊情况交给一些可以容易保证正确性的算法解决。可以视为对贪心算法的一个改进和推广。 如果说,贪心法的优势是效率高,缺点是应用范围狭小,普通算法应用范围广但是效率低下,那么部分贪心则是综合了两者,使得在正确性和算法效率之间得到了一个平衡。

一般来说,信息学竞赛需要在规定的时间限制下解决规定的题目,需要算法有很好的正确性和不错的效率。这样,部分贪心算法就是唯一能够在时间效率和正确性的双重限制下较好的解决问题的优秀算法。

应用实例及结果

这里我们通过两个例题具体分析来讨论部分贪心算法的具体应用形式。 例一、Huge Knapsack(SPOJ 699 HKNAP)

题目大意:

你来到一个地方,这个地方有N种纯金雕像,每种雕像都有无数个,每种雕像有特定的体积V[i]和重量W[i],你有S个包,每个容量为Y,每次可以花费C的代价将两个包合并成1个包,即合并3个包为1个包需要2*C的代价,问最后可以得到的金子的数目减去合并包的代价最大是多少?

数据规模:

1<= S <= 1000 000 000

1<= Y <= 1000 000 000

1<= N <= 1000

上一页第3页

你可能喜欢

  • 算法合集
  • 课程设计
  • 算法设计与分析
  • 贪心算法
  • 算法艺术与信息学竞赛
  • 常用算法

热门文档

相关文档

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