贪心算法学习总结.docx

: .
贪心算法
、算法思想贪心法的基本思路：
——从问题的某一个初始解出发逐选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩67美分，首先入选的是两枚25美分的硬币，第三枚入选的不能是5美分的硬币，否则硬币的选择将不可行（零钱总数超过67美分），第三枚应选择10美分的硬币，然后是5美分的，最后加入两个1美分的硬币。
贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。
例2［机器调度］现有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（nlogn）的贪婪算法：首先采用一个复杂性为O（nlogn）的排序算法（如堆排序）按Si的递增次序排列各个任务，然后使用一个关于旧机