在贪婪算法（greedy method）中回收慢慢结构最优解的要领。在每个阶段，都作出一个看上去最优的决定（在必然的尺度下）。决定一旦作出，就不行再变动。作出贪婪决定的依据称为贪婪准则（greedy criterion）。
例1-4 [找零钱] 一个小孩买了代价少于1美元的糖，并将1美元的钱交给售货员。售货员但愿用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步调构成要找的零钱数，每次插手一个硬币。选择硬币时所回收的贪婪准则如下：每一次选择应使零钱数只管增大。为担保解法的可行性（即：所给的零钱便是要找的零钱数），所选择的硬币不该使零钱总数高出最终所需的数目。
假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，不然硬币的选择将不行行（零钱总数高出6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后插手两个1美分的硬币。
贪婪算法有种直觉的倾向，在找零钱时，直觉汇报我们应使找出的硬币数目最少（至少是靠近最少的数目）。可以证明回收上述贪婪算法找零钱时所用的硬币数目简直最少（见操练1）。
例1-5 [呆板调治] 现有n件任务和无限多台的呆板，任务可以在呆板上得处处理惩罚。每件任务的开始时间为si，完成时间为fi ，si < fi 。[si , fi ] 为处理惩罚任务i 的时间范畴。两个任务i，j 重指两个任务的时间范畴区间有重叠，而并非是指i，j 的起点或终点重合。譬喻：区间[ 1，4 ]与区间[ 2，4 ]重叠，而与区间[ 4，7 ]不重叠。一个可行的任务分派是指在分派中没有两件重叠的任务分派给同一台呆板。因此，在可行的分派中每台呆板在任何时刻最多只处理惩罚一个任务。最优分派是指利用的呆板最少的可行分派方案。
假设有n=7件任务，标号为a到g。它们的开始与完成时间如图13-1a 所示。若将任务a分给呆板M1，任务b 分给呆板M2，. . .，任务g 分给呆板M7，这种分派是可行的分派，共利用了七台呆板。但它不是最优分派，因为有其他分派方案可使操作的呆板数目更少，譬喻：可以将任务a、b、d分派给同一台呆板，则呆板的数目降为五台。
一种得到最优分派的贪婪要领是慢慢分派任务。每步分派一件任务，且按任务开始时间的非递减序次举办分派。若已经至少有一件任务分派给某台呆板，则称这台呆板是旧的；若呆板非旧，则它是新的。在选择呆板时，回收以下贪婪准则：按照欲分派任务的开始时间，若此时有旧的呆板可用，则将任务分给旧的呆板。不然，将任务分派给一台新的呆板。 按照例子中的数据，贪婪算法共分为n =7步，任务分派的顺序为a、f、b、c、g、e、d。第一步没有旧呆板，因此将a 分派给一台新呆板（好比M1）。这台呆板在0到2时刻处于忙状态。在第二步，思量任务f。由于当f 启动时旧呆板仍处于忙状态，因此将f 分派给一台新呆板(设为M2 )。第三步思量任务b, 由于旧呆板M1在Sb =3时刻已处于闲状态，因此将b分派给M1执行，M1下一次可用时刻酿成fb =7，M2的可用时刻酿成ff =5。第四步，思量任务c。由于没有旧呆板在Sc =4时刻可用，因此将c 分派给一台新呆板（M3），这台呆板下一次可用时间为fc =7。第五步思量任务g，将其分派给呆板M2，第六步将任务e 分派给呆板M1, 最后在第七步，任务2分派给呆板M3。（留意：任务d 也可分派给呆板M2）。
上述贪婪算法能导致最优呆板分派的证明留作操练（操练7）。可按如下方法实现一个巨大性为O (nl o gn)的贪婪算法：首先回收一个巨大性为O (nl o gn)的排序算法（如堆排序）按Si 的递增序次分列各个任务，然后利用一个关于旧呆板可用时间的最小堆。
例1-6 [最短路径] 给出一个有向网络，路径的长度界说为路径所颠末的各边的淹灭之和。要求找一条从初始极点s达到目标极点d 的最短路径。
贪婪算法分步结构这条路径，每一步在路径中插手一个极点。假设当前路径已达到极点q，
且极点q 并不是目标极点d。插手下一个极点所回收的贪婪准则为：选择离q 最近且今朝不在路径中的极点。
这种贪婪算法并不必然能得到最短路径。譬喻，假设在图1 3 – 2中但愿结构从极点1到极点5的最短路径，操作上述贪婪算法，从极点1开始并寻找今朝不在路径中的离极点1最近的极点。达到极点3，长度仅为2个单元，从极点3可以达到的最近极点为4，从极点4达到极点2，最后达到目标极点5。所成立的路径为1 , 3 , 4 , 2 , 5，其长度为1 0。这条路径并不是有向图中从1到5的最短路径。事实上，有几条更短的路径存在，譬喻路径1，4，5的长度为6。
#p#分页标题#e#
按照上面三个例子，追念一下前几章所考查的一些应用，个中有几种算法也是贪婪算法。譬喻，霍夫曼树算法，操作n- 1步来成立最小加权外部路径的二叉树，每一步都将两棵二叉树归并为一棵，算法中所利用的贪婪准则为：从可用的二叉树中选出权重最小的两棵。L P T调治法则也是一种贪婪算法，它用n 步来调治n 个功课。首先将功课定时间是非排序，然后在每一步中为一个任务分派一台呆板。选择呆板所操作的贪婪准则为：使今朝的调治时间最短。将新功课调治到最先完成的呆板上（即最先空闲的呆板）。
留意到在呆板调治问题中，贪婪算法并不能担保最优，然而，那是一种直觉的倾向且一般环境下功效总长短常靠近最优值。它操作的法则就是在实际情况中但愿人工呆板调治所回收的法则。算法并不担保获得最优功效，但凡是所得功效与最优解相差无几，这种算法也称为开导式要领（ h e u r i s t i c s )。因此L P T要领是一种开导式呆板调治要领。定理9 – 2告诉了L P T调治的完成时间与最佳调治的完成时间之间的干系，因此L P T开导式要领具有限定机能（ bounded performance ）。具有限定机能的开导式要领称为近似算法（ a p p r o x i m a t i o na l g o r i t h m）。
本章的其余部门将先容几种贪婪算法的应用。在有些应用中，贪婪算法所发生的功效老是最优的办理方案。但对其他一些应用，生成的算法只是一种开导式要领，大概是也大概不是近似算法。
