案例23：在一个操场的四周摆放 N 堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。已知每堆石子数量，请选择一种合并石子的方案，使得进行N-1次合并得分的总和最小。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
对于这个问题，很人都会选择贪心算法求解——即每次选相邻和最小的两堆石子合并。对于上面的图例，利用此贪心策略的确可以找到最优解。然而本题给的样例数据实际上是一个“陷阱”，造成了用贪心法即可解决的假象。
2+3=5 5+4=9 5+4=9 9+6=15 15+9=24 总数：5+9+15+24+9=62
2+4=6 3+4=7 6+7=13 5+6=11 13+11=24 总数：6+7+13+24+11=61
案例24：在买东西时，售货员就常常计算最少需要找多少张零钱，以便简化工作流程。比如买东西需要48.5元，交给售货员100元整，按照现在的货币体系，则售货员最少需要找三张零钞：50元一张、1元一张、5角一张。
贪心算法的基本思路如下：
1）建立数学模型来描述问题。
2）把求解的问题分成若干个子问题。
3）对每一子问题求解，得到子问题的局部最优解。
4）把子问题的解局部最优解合成原来解问题的一个解。
贪心算法找最优解的必要条件
第一，原问题具有最优子结构。这样才能得到局部最优解。
第二，原问题的最优解包含了它子问题的最优解。
这样才能由局部最优合成全局最优，并且局部最优解一旦获得就不会改变。
案例25： 活动安排问题是用贪心算法有效求解的一个很好例子。活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可提供一个简单、漂亮的方法，使尽可能多的活动能兼容的使用公共资源。
设有n个活动的集合｛0，1，2，…，n-1｝，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且starti<endi。如选择了活动i，则它在半开时间区间[starti,endi）内占用资源。若区间[starti,endi)与区间[startj,endj)不相交，称活动i与活动j是相容的。也就是说，当startj≥endi或starti≥endj时，活动i与活动j相容。活动安排问题就是在所给的活动集合中选出最大的相容子活动集合。
在下面所给出的解活动安排问题的贪心算法中，设各活动的起始时间和结束时间存储于数组start[]和end[]中，不失一般性，假设结束时间安非递减排列：end[0]≤end[1] ≤…≤end[n-1]。算法中用集合a来存储所选择的活动。活动i被选择当且仅当a[i]的值为true。变量j记录最近一次选择的活动。设j是当前最近选择的活动，也就是所选择的活动中编号最大的活动，即：
j=max{i|0≤i<n,a[i]=true}
算法开始选择活动0，并将j初始化为0.然后依次检查活动i是否与当前已选择的所有活动相容。如相容则安排活动i，否则不安排活动i，再继续检查下一活动与所有已选择活动的相容性。由于k是当前已选择活动的最大结束时间，故活动i与当前所有选择活动相容的充分且必要条件是其开始时间start[i]不早于最近选择的活动j的结束时间end[j]，即start[i] ≥end[j]。若活动i满足此条件，则活动i被选择，因而取代活动j的位置。由于活动是以其完成时间的非减序排列的，所以算法每次总是选择具有最早完成时间的相容活动i。这种方法选择相容活动就使剩余活动留下尽可能多的时间。也就是该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合的活动，而空白长条表示的活动是当前正在检查相容性的活动。
活动安排问题证明贪心算法获得整体最优解
贪心算法并不总能求得问题的整体最优解，但对于活动安排问题，可以证明贪心算法能求得的整体最优解，下面将给与证明：
设E=｛0，1，2，…，n-1｝为所给的活动集合。由于E中活动安排安结束时间的非减序排列，所以活动0具有最早完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动0.设a是所给的活动安排问题的一个最优解，且a中活动也按结束时间非减序排列，a中的第一个活动是活动k。如k=0，则a就是一个以贪心选择开始的最优解。若k>0，则我们设b=a-｛k｝∪｛0｝。由于end[0] ≤end[k],且a中活动是互为相容的，故b中的活动也是互为相容的。又由于b中的活动个数与a中活动个数相同，且a是最优的，故b也是最优的。也就是说b是一个以贪心选择活动0开始的最优活动安排。因此，证明了总存在一个以贪心选择开始的最优活动安排方案，也就是算法具有贪心选择性质。