内容发布更新时间 : 2024/12/23 0:21:20星期一 下面是文章的全部内容请认真阅读。

贪心算法浅析

摘要：本文讲述了贪心算法的基本思路及实现过程，贪心算法的特点、存在的问题以及应用。

并通过贪心算法的特点举例列出了几个经典问题，通过对问题的探讨和研究，对贪心算法有了更加深入的了解。

关键词：贪心算法；最优解；最优子结构问题；删数问题；活动安排问题

贪心算法的基本思路及实现过程

1贪心的基本思想

用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。

利用贪心策略解题，需要解决两个问题： （1）该题是否适合于用贪心策略求解；

（2）如何选择贪心标准，以得到问题的最优/较优解。 2贪心算法的实现过程

（1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题； （2）从问题的某一初始解出发：

While（能朝给定目标前进一步） 求出可行解的一个解元素；

（3）由所有解元素组合成问题的一个可行解。

贪心算法的特点

贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点：

（1）如何贪心

怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。

具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。

（2）贪心的正确性

要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。

贪心算法存在的问题

（1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑；

（2）贪心算法只能用来求某些最大或最小解的问题； （3）贪心算法只能确定某些问题的可行性范围

贪心算法的应用 1哈夫曼编码

2 0-1背包问题 3磁盘文件的存储 4生产调度问题 5信息查询

贪心算法经典应用举例

删数问题

问题提出：给定n位正整数a，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。

分析：n位数a可表示为x1x2?xixjxk?xn，要删去k位数，使得剩下的数字组成的整数最小。设本问题为T，其最优解A=(y1，y2?yk)表示依次删去的k个数，在删去k个数后剩下的数字按原次序排成的新数。即最优值记为TA。

本问题采用贪心算法求解，采用最近下降点优先的贪心策略：即x1

证明：先来证明该问题具有贪心选择性质，即对问题T删除最近下降点的数xj后得到的N1是n一1位数是中最小的数。

根据数的进制特点，对a按权展开得：

a=x1*10n-1+x2*10n-2+?+xi*10n-i+xj*10n-j+xk*10n-k+?+xn 则有：Nl=x1*10n-2+x2*10n-3+?+xi*10n-i-1+xk*10n-k+?+xn 假设删去的不是xj而是其它位，则有

N2=x1*10n-2+x2*10n-3+?+xi*10n-i-1+xj*10n-k+?+xn 因为有x1xk，则有Nl

删数问题的C++代码： #include #include using namespace std;