第9讲贪心算法

1、第9讲 贪心算法,一、问题引入 例8-1工资发放问题：某单位发放员工的工资为整数，用票面为100、50、20、10、5、2、1圆的币发放，问如何发放，使得每位员工所领工资的票数最少？ 例如：发放工资2379元，票数最少时，应为100元：23张；50元：1张； 20元：1张； 5元：1张； 2元：2张。 思路分析： 我们会下意识地想到，要使总的票数最少，应当首先考虑使用大面额币值，其次考虑面额稍小一点的币值，最后面额最小的币值。,程序设计基本如下： int m,i,a7,b7=100,50,20,10,5,2,1; coutm; for(i=0;i=6;i+) ai=m/bi; m=m%bi;

2、coutbi“ : ”aiendl; ,上述寻求的票面发放思想实际上就是贪心算法。贪心算法，顾名思义，总是作出在当前看来最优的选择，并不是从总体上考虑最优，它的选择只是在某种意义上的局部最优。 例8-2假设现有四种硬币，面值二角五分、一角、五分和一分。现要找给某顾客六角三分钱，要让硬币数最少，如何找法？ 如果硬币面值改为一分、五分、一角一分三种，而找给顾客一角五分钱又如何找法？ 分析：第一个问题可就大面值币解决。第二个显然不行，而用三个五分币最隹。 总结：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解，如：单源最短路径、最小生成树问题等。在一些情况下，贪心

3、算法不能得到整体最做出解，但其结果却是最优解的很好的近似解。,二、最优解、全局最优和最优子结构概念 最优解-一个问题的求解表示成问题规模n的函数f(n),当n很大时,我们可以得到相应的下界,下界在该问题的所有算法或某类算法中复杂性中取,那么它将有意义,这时得到的下界称为问题的下界或某类算法的下界,我们就说该问题的这个特定算法是该问题的最优算法或该某类算法中的最优算法。简单说,最优算法称为最优解，有二重含义，一是达到目标时次数最少，二是同样次数数量级下，解的结果最优。例好sin(x)的算法编写，一重循环是最优解，二重循环则不是最优解。 全局最优-一个问题的考虑，从全局角度考虑，每一步或一阶段都是

4、最优的，称之为全局最优。 最优子结构-当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。,三、贪心算法的基本要素 贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能有效，然而许多情况下能达到预期目的。 对于一个具体问题，我们怎么知道可用贪心算法来求解此问题？这个问题很难给予肯定回答。 从实际经验和许多可用贪心算法求解的问题中，人们总结，它们一般具有二个重要的性质：贪心选择性质和最优子结构性质。 1、贪心选择性质 对于一个具体问题，如果我们证明

5、每一步所作的贪心选择最终导致问题的一个整体最优解时，则称此方法具有贪心选择性质。问题的贪心选择证明往往采用数学规纳法。 2、最优子结构性质,例8-3事件序列问题 已知N=12个事件的发生时刻和结束时刻（见下 表，已按结束时刻做了升序排列）。一些在时间上 没有重叠的事件可以构成一个事件序列，如事件2、 8、10，写成2，8，10。事件序列包含的事件数目 称为该事件序列的长度。请编程找出一个最长的事 件序列。,分析：用Begini表示事件i的发生时刻，Endi表示事件i的结束时刻，事件a ，b（aBegina，故 BeginaEnda BeginbEndb 对于三个事件a，b，c（abc），没有重

6、叠则同样可推出： BeginaEnda BeginbEndb BegincEndc。 本题的目标是找到一个最长的序列a1a2an，满足： Begina1Enda1 Begina2Enda2 BeginanEndan 选择策略：在可能的事件系列a1a2an选择时间上不重叠的最长系列，一定存在一个包含a1的最长系列。,证明： 确定贪心选择性质： 在当前可选的事件中，选取最先结束且与前不重叠的那个事件进入序列，不断做下去，则构成的系列一定是最长序列。 程序设计：,例8-4区间覆盖问题 用i来表示x轴上坐标为i-1,i的区间（长度为 1），并给出M个不同的整数(1M 200) ，表示M个这样的区间。现

7、在要求画几条线 段覆盖住所有的区间，条件是：每条线段任 意长，但要求所画线段的长度之和最小，并 且线段的数目不超过N（ 1N50 ） 分析：区间记录、数组设置、线段划分 确定贪心选择性质： 程序设计：,const int M=5,N=3; void main() void sort(int *a,int n); int pM=0,2,3,7,10,zc,dM-1; zc=pM-1+1; for(int i=0;iM-1;i+) di=pi+1-pi-1; sort(d,M-1); for(i=0;iN-2;i+)zc=zc-di; cout“Mini length=”zcendl; void

8、sort(int *a,int n) int i,j,t; for(i=0;in-2;i+) for(j=i+1;jn;j+ if(aiaj) t=ai,ai=aj,aj=t; ,四、贪心算法的相关理论 （1）多阶段决策问题 如果一个问题的解决过程可以分为若干阶段，在每一阶段都做出相应的决策，所有决策构成了问题的解决策略。 如果每一阶段面临的问题都是原问题的一个子问题，而且子问题的解决只与当前和以后的阶段决策有关，与以前的各阶段的决策无关，则称该问题具有无后向性特点。 （2）贪心算法解题的一般步骤,分析问题： 该问题能否满足最优化原理 问题能否转化为多阶段决策问题； 各阶段问题是否具有无后向性特点； 最优解的子问题解是否最优。 选择的策略能否得到最优解 为给出最终解或所有解