谈谈贪心算法.docVIP

PAGE PAGE 17谈谈贪心算法安师大附中 金孝岱贪心算法是一种符合人们日常思维习惯的简单有效的程序设计算法。贪心算法可用于求解最优问题。在信息学竞赛中常有它的用武之地。略举几个近年来竞赛中的题目就能见到运用贪心算法的踪影：2006冬令营《风之韵》2007 noip《纪念品分发》2007 ioi 中国队选拔赛《挂坠》2008noip《排序椅》2008ioi 《传送器》什么是贪心算法？顾名思义，贪心算法总是作出在当前看来是最好的选择。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题都能产生整体最优解或是问题的次优解。因此有很好研究它的必要。我们先来看看贪心算法在数据结构中的应用。求最小生成树的prim算法中，挑选的顶点是候选边中权值最小的边的一个端点，而加边法的kruskal算法中，更是首先将边的权值从小到大进行排序依次选取。再看看求单源最短路径的算法。其基本算法思想是：设置顶点集合s并不断作贪心选择，来扩充这个集合，以最终求得最短路径。还有哈夫曼编码也用到贪心算法。贪心算法和分治法及动态规划三者都具有子结构，都是将原问题归纳为更小规模的相似的子问题，并通过求解子问题，最后获得整体解，三者有何不同呢？只有搞清三者的区别，才能很好地运用它们来解决问题。首先是它们的子问题（或称子结构）是不同的。分治法中各子结构是独立的，动态规划一般具有重叠最优子结构，除了必须满足具有最优子结构外，还要满足无后效性。贪心算法要求问题具有最优子结构。其次，在算法实现上看，分治法一旦递归地求出各子结构的解后，便可自下而上地将这些子结构解合并成问题的解。动态规划是所有子问题只计算一次并记录下来，以备后面的子问题使用，用空间换取时间, 所以求当前的解要依赖前面子结构的解。一般采用自底向上的递推方式求解。贪心法则是从上而下，从问题的初始阶段开始每个阶段作一个贪心的选择，不断将问题转换为规模更小的子问题，并期望通过每一次的局部最优选择达到全局最优。贪心算法具有两个重要性质：①最优子结构性质②贪心选择性质用好贪心算法关健是对一个问题能否运用贪心算法的判断和贪心标准的设计。对于一个问题能否用贪心算法要给出严格的证明是件比较困难的事，借助一个称为“拟阵”的工具，可以建立一个关于贪心算法的较一般的理论。这个理论在确定何时使用贪心算法可以得到问题的整体最优解十分有用。但是比较深奥难以理解。我们主要还是根据贪心算法的两个性质，以及运用反证法来证明。更重要的是要通过编程实践多摸素、总结，从而掌握贪心算法。另外运用贪心算法的思想与其它算法相配合，如“枚举+贪心”，“启发+随机化”多次贪心以及用于分支定界上等都有很好的效果。下面通过一些例题来看看如何运用贪心算法。例1.背包问题【题目描述】 这是一大家很熟悉的背包问题。给定n种货物和一个载重量为m的背包。已知第i种货物的重量为wi ,其总价值为pi，编程确定一个装货方案，使得装入背包中货物的总价值最大。输出此总价值和装货方案。【算法分析】0，1背包问题对每种物品只有两种选择：选和不选，可用动态规划解决。而背包问题，可以选择物品的一部分装载，这样就可以把背包装满，用贪心算法可求得最优解。采用贪心标准是：选择单位重量价值高的货物优先装入，这样才能保证背包中所装货物总价值最大。而0，1背包用贪心算法却不能得到整体最优，为什么呢？我们来看一个例子： 有一背包容量为50千克，有三种货物：物品1重10千克；价值60物品2重20千克，价值100物品3重30千克；价值120202010总价值：（用贪心算法）80+100+60=240对于0，1背包问题，贪心选择之所以不能得到最优解是因为它无法保证最终将背包装满，部分背包的 闲置使单位重量背包空间的价值降低。例2．排队问题【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0i=n）,请求出一种排列次序，使每个人排队等候时间总和最小。输入数据：第1行一个正整数n（你=10000》，第2行有n个不超过 1000的正整数ti.输出要求：n个人排队时间最小总和。输入输出样例输入：45 10 8 7输出：67【算法分析】本题贪心算法：n个人时间从小到大排序，就是这n个人最佳排队方案。求部分和的和即为所求。反证法证明：假设有最优解序列：s1,s2…sn,如s1不是最小的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的人无影响，对sk之前的人等待都减少了，(s1-sk)0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。例3．:数列极差问题【题目描述】 在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b