贪心算法解题的基本思路

先看一个小例子，假如一个小孩去商店买圆珠笔，他拿了10元钱给售货员，圆珠笔的价钱是2元3角，售货员需要找给小孩7元7角。现在，售货员手中只有5元、1元、5角和1角的钱币。在小孩的催促下，售货员想尽快将钱找给小孩。她该如何做？

她的做法是：先拿一张不大于7元7角的最大钱币——5元钱币，再拿两张不大于（7元7角-5元）=2元7角的最大钱币——1元钱币，再拿不大于（2元7角-1元-1元）=7角的最大钱币——5角钱币，最后售货员再拿出两个1角的钱币。至此，售货员共找给小孩6枚钱币。

售货员的原则是尽量快地找钱，也就是拿尽可能少的钱币个数找给小孩。从另一个角度看，如果售货员将捡出的钱币逐一放在手中，最后一起交给小孩，那么售货员想使自己手中的钱数增加得尽量快些，尽快达到找钱的总数，所以每一次都尽可能地捡面额大的钱币。这就是贪心算法的基本思路。

贪心算法总是作出在当前看来最好的选择。也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。贪心算法解题的基本过程是通过做出在当前看来最优的选择（贪心选择），完成原问题的一部分，使问题规模缩小，继续进行贪心选择，如此反复，直至得到最终解。

能够用贪心算法解决的问题有以下两个基本特征。

（1）贪心选择性质，所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。(www.xing528.com)

（2）最优子结构性质，当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。亦即，通过局部最优选择，原问题将被化简为类似的子问题；整体最优解中包含了子问题的最优解。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

具有这两个特征的问题用贪心算法来解决的一般步骤如下。

步骤1：做出当前最优选择。

步骤2：若问题已解决，则完成。若问题尚未解决，转步骤1。