第9讲贪心算法.ppt

第9讲 贪心算法 一、问题引入 [例8-1]工资发放问题：某单位发放员工的工资为整数，用票面为100、50、20、10、5、2、1圆的币发放，问如何发放，使得每位员工所领工资的票数最少？ 例如：发放工资2379元，票数最少时，应为100元：23张；50元：1张； 20元：1张； 5元：1张； 2元：2张。 思路分析： 我们会下意识地想到，要使总的票数最少，应当首先考虑使用大面额币值，其次考虑面额稍小一点的币值，最后面额最小的币值。 程序设计基本如下： int m,i,a[7],b[7]={100,50,20,10,5,2,1}; cout“input salary m=”; cinm; for(i=0;i=6;i++) { a[i]=m/b[i]; m=m%b[i]; coutb[i]“ : ”a[i]endl; } 上述寻求的票面发放思想实际上就是贪心算法。贪心算法，顾名思义，总是作出在当前看来最优的选择，并不是从总体上考虑最优，它的选择只是在某种意义上的局部最优。 [例8-2]假设现有四种硬币，面值二角五分、一角、五分和一分。现要找给某顾客六角三分钱，要让硬币数最少，如何找法？ 如果硬币面值改为一分、五分、一角一分三种，而找给顾客一角五分钱又如何找法？ 分析：第一个问题可就大面值币解决。第二个显然不行，而用三个五分币最隹。 总结：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如：单源最短路径、最小生成树问题等。在一些情况下，贪心算法不能得到整体最做出解，但其结果却是最优解的很好的近似解。 二、最优解、全局最优和最优子结构概念 最优解---------一个问题的求解表示成问题规模n的函数f(n),当n很大时,我们可以得到相应的下界,下界在该问题的所有算法或某类算法中复杂性中取,那么它将有意义,这时得到的下界称为问题的下界或某类算法的下界,我们就说该问题的这个特定算法是该问题的最优算法或该某类算法中的最优算法。简单说,最优算法称为最优解，有二重含义，一是达到目标时次数最少，二是同样次数数量级下，解的结果最优。例好sin(x)的算法编写，一重循环是最优解，二重循环则不是最优解。 全局最优--------一个问题的考虑，从全局角度考虑，每一步或一阶段都是最优的，称之为全局最优。 最优子结构------当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 三、贪心算法的基本要素 贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能有效，然而许多情况下能达到预期目的。 对于一个具体问题，我们怎么知道可用贪心算法来求解此问题？这个问题很难给予肯定回答。 从实际经验和许多可用贪心算法求解的问题中，人们总结，它们一般具有二个重要的性质：贪心选择性质和最优子结构性质。 1、贪心选择性质 对于一个具体问题，如果我们证明每一步所作的贪心选择最终导致问题的一个整体最优解时，则称此方法具有贪心选择性质。问题的贪心选择证明往往采用数学规纳法。 2、最优子结构性质 [例8-3]事件序列问题 已知N=12个事件的发生时刻和结束时刻（见下 表，已按结束时刻做了升序排列）。一些在时间上 没有重叠的事件可以构成一个事件序列，如事件2、 8、10，写成{2，8，10}。事件序列包含的事件数目 称为该事件序列的长度。请编程找出一个最长的事 件序列。 分析：用Begin[i]表示事件i的发生时刻，End[i]表示事件i的结束时刻，事件a ，b（ab，表示b在a之后结束）没有重叠，则 End[a] ≤Begin[b] 由于End[a] Begin[a]，故 Begin[a]End[a] ≤Begin[b]End[b] 对于三个事件a，b，c（abc），没有重叠则同样可推出： Begin[a]End[a] ≤Begin[b]End[b] ≤Begin[c]End[c]。 本题的目标是找到一个最长的序列a1a2……an，满足： Begin[a1]End[a1] ≤Begi