贪心算法

IT商界

PALADIN

　　上期我们说了动态规划算法，本期我们来说说与动态规划算法有很多相似处的贪心算法。

　　贪心算法在我们的生活中，常常被用到。现实生活中，在我们买东西找零钱时，大家就会不自觉地用到贪心算法。例如要找5角8分钱(如果可选的有5角、1角、5分、2分、1分的硬币)，我们很自然地就会想到要找一个5角、一个5分，一个2分以及一个1分的硬币。这样的找钱方式比其他的找钱方法相比，所拿出的硬币个数是最少的。我们所用的找硬币的方法是：首先选出一个面值不超过要找的5角8分的最大硬币，即5角，这样余下8分。再选面值不大于8分的最大硬币5分，余下3分。以此类推最终确定所有的硬币。

　　可以看出，贪心算法总是做出在当前看来是最好的选择，而并不是从整体的思想上考虑最优解，但它往往是某种意义上的局部最优选择，所以贪心算法并不总能保证获得整体的最优解。这正是贪心算法与动态规划算法区别所在，也是判断是否能用贪心算法的依据所在。

　　在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，凭着当前的状态就做出在当前看来是最好的选择，即局部最优选择。然后再去解出这个选择后产生的相应的子问题。通俗点说就是，贪心算法作选择时，是根据过去的选择，但决不依赖于将来未知的选择或未解问题的解。所以动态规划算法通常是以自底向上的方式解各子问题，而贪心算法则通常是自顶向下，以迭代的方式依次做出选择，每作一次贪心选择就使得待解问题的规模变小一些。当然，贪心算法同动态规划算法一样，都具有最优子结构性质。关于最优子结构性质我在讲动态规划时已经讲过，这里不再赘述。

　　尽管在有些场合，贪心算法不是很适用，但解决会场安排活动的问题，是用贪心算法有效求解的一个很好的范例。该问题是要求在某个会场安排一系列的活动，并且会场不能同时安排任意两个活动。已知n个活动，并且第i个活动要求开始的时间是bi，结束的时间是ei，为了达到高效安排的目的(尽可能多地安排活动)，我们可以使用贪心算法来安排活动。

　　首先，我们参照已知活动的结束时间，按照从前往后的顺序对它们进行排序，使得重排的序列满足e1≤e2≤……≤en。这样，对于重排后序列，我们首先选择安排活动1，然后依次检查活动i是否与当前已选择的所有活动相容。若相容则活动i加入到已选择活动的集合中，否则不选择该活动。然后继续检查下一个活动。算法的伪码设计如下：

　　procedure huodong(b,e,A) //b、e分别是按照活动结束时间进行非减排序后的所有活动的开始结束时的数组，A是安排活动的集合

　　begin

　　A←{1}; //将第1项活动放入A

　　j:=1; //j记录下最后安排的活动序号，开始时是1

　　for i;=2 to n do

　　begin

　　if b[i]≥e[j] then //如果当前的活动的开始时间比结束的时间要晚就安排该活动

　　begin

　　A←A∪{i};

　　j:=i; //记录该活动序号

　　end;

　　end;

　　end;

　　本月有奖题目：

　　已知一辆汽车要从A地前往B地，而旅途中有M个加油站，已知这M个加油站分别到A地距离为S1、S2 ……Sm。该车加满油后可行驶N公里，车从A地地开出时已加满了油。设计一个程序，输入N以及S1、S2 ……Sm，输出该车应在哪些加油站停靠加油，使沿途加油次数最少。并证明该方法获得的是最优解。

　　读者朋友可以用你最擅长的语言和编程工具来完成这道题，答题方式为：把你的答案发送到software@cpcw.com，邮件主题写上“算法演义答题”。我们会从中选取答题最好的参赛者，并发送精美奖品。