阜阳市第三中学 安徽阜阳 236000

贪心算法是一种非常常见的算法，最常应用的有归纳法和反证法，当然还有其它的应用方式。此外，贪心算法是信息竞赛中最为常用的一种解题思路。

1 贪心算法的定义

贪心算法只是当下最优的一种解题方式，与后续无关，有些自私因素在其中，所以被称为贪心算法[1]。因为其局部性，可能从整体来看这种解题方式不够完美、不够准确，但它是目前最快最完美的解答方式。这种方式在信息竞赛中很常见，也是信息竞赛中的一种常见解题思想。

2 贪心算法的基本要素

贪心算法的第一个要素是贪心选择，通常来说就是所求问题的一种最优的解答方式。一般是我们常采用从顶向下，或者是以迭代的方式做出选择，但都是为了同一目的，之后再通过一次次贪心选择，将求解的问题不断做减法，通过简化，缩小规模以找寻最优的一种解题方法。

一般来说，一个问题能否用贪心算法，首选要看它能否做出贪心选择，如果可以通过一步步的贪心选择，最终找到最优方式，那么就可以使用贪心算法。通过数学归纳法来证明，就是每一步的贪心选择最后都是为了达到最优的目的。而使用贪心算法一般都有一定的贪心策略，而证明这个贪心策略的方法有很多，一般最常用的有归纳法、反证法。

3 贪心算法生活中的应用

在日常生活中，比如汽车去加油站加油，如果加满后这辆车可以行驶N千米，但是在途中有很多个加油站，此时我们可以利用贪心算法算出在整个旅途中怎么加油使得加油的次数最少。……