第4章 贪心算法

1、第4章 贪心算法,4.1 什么是贪心法 4.2 贪心法的典型示例 本章小结,4.1 什么是贪心法,4.1.1 复杂问题的求解方法 4.1.2 贪心法的设计思想 4.2.3 几个例子 4.2.4 小结,4.1.1 复杂问题的求解典型方法,分治法 将复杂问题分成若干个相互独立的子问题，通过求解子问题，并将子问题的解合并得到原问题的解。 动态规划法 将一个复杂问题分解为若干个相互重叠的子问题，通过求解子问题形成一系列决策得到原问题的解。,4.1.1 复杂问题的求解典型方法,贪心法（Greedy Method） 将一个复杂问题分解为一系列较为简单的局部最优选择，每一个选择都是对当前解的一个扩展，直到获

2、得问题的完整解。 搜索法,4.1.2 贪心法的设计思想,基本思想 将问题的求解过程看作是一系列选择，每次选择都是当前状态下的最好选择(局部最优解)。 每作一次选择后，所求问题会简化为一个规模更小的子问题，从而通过每一步的最优解逐步达到整体的最优解。,4.1.2 贪心法的设计思想,特点 贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 换言之： 贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。,4.2.3 几个例子,例1：数字三角形问题 例2：渴婴问题 例3：找零钱问题,例1：数字三角形问题,数字

3、三角形问题 穷举法 动态规划法 89：13-11-26-15-24 贪心法 63：13-11-12-14-13,例2：渴婴问题,问题描述 已知： 饮料类型： n 饮料满意度： s1 , s2, , si , , sn 饮料总量 ： a1 , a2, , ai , , an 需求： t 问： 需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求，而且能达到最大的满意程度呢？,例2：渴婴问题,问题分析： 令：xi 为婴儿将要饮用的第i 种饮料的量 则：需要解决的问题是找到一组实数xi （1in）,例2：渴婴问题,解决方案： 分步获取饮料，每次喝一种饮料，且需要考虑选用哪种饮料； 根据这种思想，利用

4、如下的贪心准则： 从余下的饮料中，选择满意度最高的饮料，直到达到解渴的需要，或者全部饮料被喝完为止。,例3：找零钱问题,问题描述 假如售货员需要找给小孩98元的零钱，售货员手中有1、2、5、10、20、50元的零钱若干。 在小孩的催促下，售货员想尽快将钱找给小孩。 分析： 贪心准则： 每一次选择应使零钱数尽量增大。 为保证解法的可行性（即：所给的零钱数等于要找的零钱）每次所选择的硬币不应使零钱总数超过最终所需的数目。 具体做法： 985020 20 52 1,4.1.4 小结,思想 由一系列步骤构成 每步满足 可行：满足问题的约束条件 局部最优：当前状况下的最优解 不可取消：一旦作出选择，不可

5、更改 求解问题的类型 局部最优导致全局最优（最优解） 局部最优接近全局最优（近似解），但速度极快 优点 求解速度快，时间复杂性有较低的阶 。,4.1.4 小结,贪心法的基本要素: 具备贪心选择性质和最优子结构性质的最优化问题。,整体的最优解可通过一系列局部最优解达到。每次的选择可以依赖以前作出的选择,但不能依赖于后面的选择。,问题的整体最优解中包含着它的子问题的最优解.,4.2 贪心法的典型应用,组合问题中的贪心法 图问题中的贪心法 其他问题,应用专题一,组合问题中的贪心法 例1：活动安排问题 例2：最优装载问题 例3：01背包问题 例4：背包问题 贪心法与动态规划法的异同点 例5：多机调度问

6、题,例1：活动安排问题,问题提出： n个活动的集合E=1,2,n 每个活动i 要求使用资源的时间：si, fi) 活动i与活动j是相容的： 若区间si, fi)与区间sj, fj)不相交，称活动i与活动j是相容的。 活动安排问题：在所给的活动集合中选出最大的相容活动子集合。即：要求高效地安排一系列争用某一公共资源的活动。,例1：活动安排问题,分析： 安排活动时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的时间，从而达到安排最多活动的目标。 贪心准则 在未安排的活动中挑选结束时间最早的活动安排。 将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结

7、束时间非减排列：f1 f2 fn。,例1：活动安排问题,例如：,1 2 3 4 5 6 7 8 9 10 11,2,4,5,6,1,3,7,例1：活动安排问题,算法描述： int greedySelector(int s , int f , bool a ) a1=true; int j=1,count=1; for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; ,例1：活动安排问题,算法时间分析： 算法greedySelector的效率极高。 当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排

8、n个活动，使最多的活动能相容地使用公共资源。 如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,例1：活动安排问题,利用数学归纳法可以证明： 贪心算法greedySelector总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。,例1：活动安排问题,练习： 已知待安排的11个活动的开始时间和结束时间，并且已经按结束时间的非减序排列如下：,例1：活动安排问题,习题4-1,活动安排问题的贪心选择方案 具有最短时段的相容活动 覆盖未选择活动最少的相容活动,算法实现题4-1,会场安排问题 算法1：用算法GreedySelector来安排会场 算法2： 对n个活动看做是实

9、直线上的n个半闭活动区间，问题的实质是讨论n个活动区的最大重叠数m。 若求得了最大重叠数m，则这m个重叠区所对应的活动互不相容，因此至少要安排m个会场来容纳这n个活动。 （1）将活动的开始和结束时间进行排序 （2）扫描整个实直线，遇到一个si,则安排一个空闲会场，遇到一个fi,就释放一个会场为空闲备用。,例2：最优装载,问题描述 有一批集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi （1in） 。 最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,例2：最优装载,分析： 这个问题可以作为最优化问题进行描述：,例2：最优装载,解决方案： 船可以分步装载，每

10、步装一个货箱，且需要考虑装载哪一个货箱。 贪心准则： 从剩下的货箱中，选择重量最小的货箱。 这种选择次序可以保证所选的货箱总重量最小，从而可以装载更多的货箱。,例2：最优装载,例如： n 8 w100,200,50,90,150,50,20,80, c400。 按照重量贪心原则，确定装载方案。 解： 所考察货箱的次序 :7, 3, 6, 8, 4, 1, 5, 2， 最优解x= 1, 0, 1, 1, 0, 1, 1, 1。,例2：最优装载,算法描述： template void Loading(int x , Type w , Type c, int n) int *t = new int

11、n+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n ,例2：最优装载,分析： 最优装载问题满足贪心选择性质和最优子结构性质，故算法正确，能求得最优解。 时间复杂性： 算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。,例3：0-1背包问题,问题描述： 给定n个物品和一个背包，物品 i 的重量为wi ,其价值为vi ,背包的容量为c。 问:如何装物品，使得装入背包中物品总价值最大？,例3：0-1背包问题,分析 解决方案： 分步装入，在每一步

12、过程中利用贪心准则选择一个物品装入背包。 至少有三种看似合理的贪心策略： （1）重量贪心准则 （2）价值贪心准则 （3）价值密度贪心准则,例3：0-1背包问题,三种策略都不能保证得到最优解,例3：0-1背包问题,分析： 三种贪心策略都不能保证得到最优解的原因 重量贪心准则 价值贪心准则 价值密度贪心准则 对于01背包问题，贪心选择不能得到最优解的原因是它无法保证最终能将背包装满。 部分闲置背包空间使单位重量背包空间所具有的价值降低了。,例3：0-1背包问题,事实上: 在考虑01背包问题的物品选择时，应比较选择该物品和不选择该物品所导致的最终结果，然后再作出最好选择。 由此导出许多互相重叠的子问

13、题。 这正是动态规划法求解问题的一个重要特征。 动态规划法可以有效地解决01背包问题。,例4：背包问题,问题描述： 给定n个物品和一个背包，物品 i 的重量为wi ,其价值为vi ,背包的容量为c。 问:如何装物品，使得装入背包中物品总价值最大？,例4：背包问题,分析： 贪心准则 重量 价值 价值密度 可以证明： 按价值密度（单位价值）作为度量标准，背包问题达到最优解。,例4：背包问题,例如：,例4：背包问题,算法描述 void Knapsack(int n,float M,float *v,float * w ,float *x) Sort(n, v, w); /按单位价值排序/ for (

14、i =1;i c) break; xi= 1; /放入物品i c-= wi; if(i= n) xi = c/wi; ,例4：背包问题,算法分析: 排序为主要算法时间，故：T(n)=O(nlogn) 。,贪心法与动态规划法的异同点,相同点 要求问题具备最优子结构性质。 不同点 动态规划算法的另一个基本要素是重叠子问题性质，通常以自底向上的方式解各子问题。 贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 （贪心选择性质）,例5：多机调度问题,问题描述： 多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内

15、由m台机器加工处理完成。 约定： 每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。 作业不能拆分成更小的子作业。,例5：多机调度问题,解决方案 贪心算法 短时优先 需要短处理时间作业优先处理 长时优先 需要长处理时间作业优先处理 注： “长时优先”的贪心选择策略可以设计出解多机调度问题的较好的近似算法。,例5：多机调度问题,“长时优先”贪心算法的求解分析： 当nm时： 首先将n个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机，算法需要O(nlogn)的计算时间。,例5：多机调度问题,例如： 设7个独立作业1,2,3,4,5,6,7，所需的处理时间分别为

16、2,14,4,16,6,5,3，由3台机器M1M3加工处理。,J4,J2,J7,J5,J6,J3,J1,应用专题二,图问题中的贪心法 例1：Huffman 编码问题 例2：单源点最短路径问题：Dijkstra算法 例3：最小生成树问题：Prim算法 例4：TSP问题,例1：Huffman编码,问题提出: 通讯过程中需将传输的信息转换为二进制码。由于英文字母使用频率不同，若频率高的字母对应短的编码，频率低的字母对应长的编码，传输的数据总量就会降低。要求找到一个编码方案,使传输的数据量最少。 分析： 为能正确译码，编码需采用前缀码，前缀码和二叉树一一对应。问题可化为求一棵最优二叉树。,例1： Hu

17、ffman编码,贪心选择性 设T为带权w1w2. wt的最优树， 带权w1和w2的树叶vw1和vw2是兄弟。 以vw1和vw2为儿子的分枝点,其通路长度最长。 最优子结构: 设T为带权w1w2. wt的最优树，若将以带权w1和w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵新树T，则T也是最优树。,例1： Huffman编码,Huffman算法 例如： 求带权为2,2,3,3,5的最优二元树.,例2：单源点最短路径,问题描述 设给定一个带权有向图G=V，E，指定G中一个顶点 vs为源点,现在要求出从vs到图中其余各个顶点之间的最短路径，该问题称为单源点最短路径问题。 Dijkstra

18、算法 从图中的给定源点vs到其他各个顶点之间客观上应存在一条最短路径，在这组最短路径中，按路径长度递增次序，依次求出到不同顶点的最短路径长度。,例2：单源点最短路径,基本思想： 设置一个顶点集合S并不断作贪心选择来扩充该集合。 Step1：初始时 S=vs， 设置距离数组dist 设u是G的某一顶点， distu记录vs到u且中间只经过S中顶点的路径的长度。 Step2：从VS中取出最短路径长度的顶点u，将u添加到S中，同时对数组dist做必要的修正。 Step3：算法重复Step2 ,直到S=V，dist就记录了从vs到所有其他顶点之间的最短路径长度。,例2：单源点最短路径,例：单源点最短路

19、径算法运行实例。,v2,v4,v3,v5,v1,例3：最小生成树,基本定义 子图 生成子图 生成树,例3：最小生成树,基本定义 子图 生成子图 生成树 一个连通无向图G=(V, E)，边权为W=W1,W2,Wn-1，且 T 是 G 的生成树，其边权总和记为： W(T)。 最小生成树 T*：,例3：最小生成树,最小生成树的性质 设一个连通带权图G=(V, E)，S是V的一个真子集。 如果边(u, v)E 且 u S, v VS, 而且所有这样的边(u, v)的权cuv最小，则一定存在G的一棵最小生成树，它以(u, v)为其中的一条边。 证明：,例3：最小生成树,分析： 获得最小生成树的贪心方法是

20、按照边的成本的和有最小增量为度量标准，逐条边地构造这棵树。 根据使用贪心策略的不同，可以分为： Prim 算法 Kruskal 算法。,例3：最小生成树,Prim算法 基本思想： 先置S=1， 只要S是V的真子集，就作如下的贪心选择： 选取满足条件i S, j VS且权cij最小的边，并将顶点j添加到S中， 直到S = V为止。 注意：T始终是一棵树。,例3：最小生成树,算法描述 void Prim() T= ; / T存放最小生成树的边 S =1；/ S存放最小生成树的顶点 while(S!=V) ( i, j ) = i S, j VS的最小权边； T = T ( i, j )； S =

21、S j; ,例3：最小生成树,Prim算法过程示例：,v1,例3：最小生成树,Kruskal算法 T=V，； (u0,v0)= min(cost(u,v) |u，v分属不同的连通分量,将边(u0,v0 )并入T的边集合TE； 重复第2步，直至所有顶点在同一个连通分量中为止。 注意： 生成最小生成树的过程中，T一般是森林，最后才变为一棵树。,例3：最小生成树,算法描述 void Kruskal() T= ; / T存放最小生成树的边 while( T的边少于n1) 从边集E中选一条最小权边( v, w )； 从边集E中删去边( v, w )； if （边( v, w )在T中不生成环） 将( v

22、, w )加到T； else 舍弃( v, w )； ,例3：最小生成树,Kruskal过程示例：,例4： TSP问题,问题描述,例4： TSP问题,分析： 求解TSP问题至少有两种贪心策略是合理的贪心策略 贪心策略1：最近邻点策略 贪心策略2：最短链接策略,贪心策略1：最近邻点策略,最近邻点策略： 从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。 例如：,贪心策略1：最近邻点策略,贪心策略1：最近邻点策略,算法： 输入:城市的数目n,代价矩阵c,起点城市v0 输出: 最小代价路线tour，cost为最小代价 tour=0; cost=0; v=v

23、0 ; V=V-v0; for （ k=1；kn;k+) /查找与顶点v邻接的最小代价边(v, w)并且wV； tour+= (v,w) ; cost+= c(v,w) ; v=w; V=V-w; tour+=(v, v0); cost+= c(v, v0) ; printf( tour, cost )；,贪心策略1：最近邻点策略,分析 算法的时间复杂度O(n2) 注意： 用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解，上图从城市1出发的最优解是125431，总代价只有13。 当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程

24、度近似于最优解，却难以保证。,贪心策略2：最短链接策略,最短链接策略 每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。 因此，当从剩余边集E按照权值中选择一条边(u, v)加入解集合S中，并尽可能权值小的边。应满足以下条件： 边(u, v)加入解集合S后，S中不产生回路； 边(u, v) 加入解集合S后，S中不产生分枝； 使权值尽可能小。,贪心策略2：最短链接策略,例如：,贪心策略2：最短链接策略,贪心策略2：最短链接策略,算法描述： 顶点数:n ,代价矩阵:c ,E:候选边集合,P:经过的边集。,贪心策略2：最短链接策略,算法的时间性能分析：

25、 对于“两个顶点是否连通以及是否会产生分枝”的操作 可以用并查集的操作将其时间性能提高到O(n)； 如果操作“ 在E中选取最短边(u, v) ” 用顺序查找，则选取最短边的操作可以是O(n)，此时算法的时间性能为O(n2)。 如果采用堆排序的方法将集合E中的边建立堆，则选取最短边的操作可以是O(log2n)，此时算法的时间性能为O(nlog2n)。,应用专题三,贪心策略： 不仅仅可以应用于最优化问题中； 有时在解决构造类等问题时，用这种策略可以尽快地构造出一组解。 其他应用专题 例1：汽车加油问题 例2：旅行家的预算 例3：数列极差问题 例4：删数问题 例5：真分数分解问题 例6：币种统计问题

26、,例1：汽车加油问题,问题描述 一辆汽车加满油后可以行驶nkm。旅途中有若干加油站。设计一个有效算法指出应在哪些加油站停靠加油，使沿途加油次数最少。 分析 贪心原则 例如 输入:输出 7 74 1 2 3 4 5 1 6 6,例2：旅行家的预算,问题描述： 一个旅行家想驾驶汽车以最少的费用从一个城市到达第二个城市（假设出发前油箱是空的）。 给定两个城市之间的距离d， 汽车油箱的容量c， 每升汽油能行驶的距离 m， 出发点每升汽油的价格p0和沿途的加油站数目k， 油站i离出发点的距离为di 每升汽油的价格pi(i=1,2,k)。 要求输出最小费用及加油方案。,例2：旅行家的预算,分析：,已知pi

27、:表示第i站的油价 di:表示第i站距离出发点的距离 设overi:表示第i站的余油量 xi:表示第i站的加油量 则 ： 最省的加油方案是一组（x0,x1,x2,xk+1)，使满足：,例2：旅行家的预算,考虑如下问题 出发前汽车的油箱是空的，那么汽车在起点处加油的量为多少？ 行程到第几站开始加油，加多少油？ 一般地： 对于加油站i，下一个加油站j的油价低于加油站i（油箱需要(djdi)/m升汽油， 若不能到达这样的油站，则至少需要到达下一个油站i+1后，继续进行考虑，此时应加满油箱。,例2：旅行家的预算,算法描述： i=0;over =x =0;L=c*m; do 若（di+1diL） 输出无

28、解，返回； 在L内查找第1个低于i站油价的油站j; if (j存在) if (overi 能到达j) 计算到达j的余油overj else 在i站购买油xi，使其刚好到达j站 else 在i站加满油,到达i+1站,并计算i+1站的余油 while 未到达终点；,例3：数列极差问题,问题描述： 在黑板上写了N个正整数作成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数ab+1，如此下去直至黑板上剩下一个数。 在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min， 则该数列的极差定义为M=maxmin。,例3：数列极差问题,问题分析 我们通过实例来认

29、识题目中描述的计算过程。 对三个具体的数据3，5，7讨论，可能有以下三种结果： （351）71113 （371）51111 （571）31109 由此可见：先运算小数据得到的是最大值，先运算大数据得到的是最小值。,例3：数列极差问题,一般地： 任意三个数a,b,c，不妨假设abc： 则有以下几种组合计算结果： (a*b+1)*c+1=a*b*c+c+1 (a*c+1)*b+1= a*b*c+b+1 (b*c+1)*a+1= a*b*c+a+1 显然此问题适合用贪婪策略 不过在求最大值时，要先选择较小的数操作。 反过来求最小值时，要先选择较大的数操作。 这是一道两次运用贪心策略解决的问题。,例3

30、：数列极差问题,算法设计 问题的解决方法和huffman树的构造过程相似。 选取最大和最小的两个数 二分法 简单的逐个比较的方法来求解。 注意：求max、min的过程必须独立 算法分析 时间复杂度T(n)=O(n)。 空间复杂度S(n)=O(n)。,例4：删数问题,问题描述： n位整数a，去掉其中任意k个数字后，剩下的数字按原次序组成一个新的正整数。 设计一种最小删数方案，使得剩下得数字组成的新数最小。 问题分析 贪心法求解：删k个数符的全局最优解，包含了删除1个数符的子问题的最优解。 以字串形式输入a，使用尽可能逼近目标的贪心法来逐一删去其中的k个数符，每一步总是选择一个能使剩下的数最小的数

31、符删去。,例4：删数问题,例如： a=178543 ，k=4 a=278594513，k=6 贪心准则： 最近下降点优先 按照高位低位搜索递减区间，若存在递减区间，则删去该区间的首字符；否则删去尾字符。 重复上述规则，删下一个字符，依此类推，直至删去k个字符为止,例5：真分数分解,问题描述： 设计一个算法， 把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的形式。 如：7/8=1/2+1/3+1/24。 问题分析 基本思想： 逐步选择分数所包含的最大埃及分数，这些埃及分数之和就是问题的一个解。 如： 7/81/2 7/81/21/3 7/81/21/31/24。 故：7/8 1/21/31/24。,例5：真分数分解,问题的求解过程： (1)找最小的n（也就是最大的埃及分数），使