在某些数据规模非常大的问题当中,我们常常希望使用贪心法解决问题,但是纯粹的贪心在某些情形下会有反例存在。在这些情况下,我们可以采取一种折中的方案——部分贪心。降问题规模降低到较小的范围内以后,再采用其他方法解决。
中间的状态则采用贪心思想解决。这样平衡了算法的效率和正确性,得到了一个相对理想的结果,这种算法便是部分贪心算法。
举一个例子:求函数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
【关键字】 部分贪心 【正文】 引言贪心在信息学竞赛中,是一种非常重要的思想。 一般来说,如果贪心算法可以证明其正确性,那么时间复杂度将远远优于其它算法。 但是...
引入– –– 众所周知,贪心算法是一个在信息学竞赛中应用广 泛的高效算法。 ...? 针对这一思想,我们很容易设计出一个贪心算 法——枚举一条边做往复运动,...
引入– –– 众所周知,贪心算法是一个在信息学竞赛中应用广 泛的高效算法。 ...? 针对这一思想,我们很容易设计出一个贪心算 法——枚举一条边做往复运动,...
部分贪心在信息学竞赛中的应用 北京市清华附中 高逸涵 引言 ? 引入– –– 众所周知,贪心算法是一个在信息学竞赛中应用广 泛的高效算法。 但是有的时候,由于...
部分贪心算法思想在信息学... 7页 2财富值 (NOIP)信息学竞赛 贪心算法... 29页 20财富值 最大流在信息学竞赛中应用 15页 1财富值 信息学竞赛常用的算法...
贪心策略的特点与在信息学竞赛中的应用_IT/计算机_专业资料。经典的贪心算法... 部分贪心算法思想在信息... 7页 1下载券 信息学竞赛3 - 8贪心 暂无评价 ...
浅谈贪心策略的特点与在信息学竞赛中的应用_天文/地理_自然科学_专业资料。...(贪 心选择性质和局部最优解)介绍了 3 种体现"贪心"思想的图形算法:Dijkstra...
算法合集之《浅析倍增思... 35页 免费 部分贪心算法思想在信息... 7页 1...IOI2004 国家集训队论文 肖天 “分层图思想”及其在信息学竞赛中的应用天津市...
部分贪心算法思想在信息学... 7页 2财富值 (NOIP)信息学竞赛 贪心算法......用最少的船装载所有人; 贪心策略:乘船问题:最轻的人和尽量重的人配对; 应用...
算法合集之《浅谈数形结合思想在信息学竞赛中的应用》_IT/计算机_专业资料。摘要 数与形是数学中两个最古老而又最基本的对象,数形结合又是一种重要的数学思想...
热门文档