算法设计与分析 课件 许瑾晨 第六章 贪心算法

信息工程大学算法设计与分析贪心法国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版仅有动态规划是不够的动态规划是对分治思想的一种改善，它在发现分解出来的子问题有重叠时，保存子问题的结果避免重复计算，从而提升了算法的效率。但避免重复计算并不是最高明的策略。

动态规划的特点是在每次做选择前，将所有可能的情况进行计算，在此基础上选择能够达到最优的选项。

本章学习的贪心算法策略：不考虑所有可能情况，只是做出当前看来是最好的选择！引例找零钱问题原理和方法两个重要性质最优子结构贪心选择贪心法正确性证明典型应用部分背包活动安排过河问题哈夫曼编码最小生成树多机调度信息工程大学算法设计与分析贪心法—引例—找零钱问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版假设要找给顾客6.3元，现在你手头有面值为2.5元、1元、5角和1角的硬币若干，试问如何找钱使得所找的硬币总数最少？策略：优先使用面值大的硬币

2个2.5元的硬币1个1元的硬币3个1角的硬币与其它找法相比，这种找法拿出来的硬币个数最少。目标：找出的硬币个数最少策略：优先选用大面值硬币思考：该策略总是可以得到最优解吗？贪心法假设要找给某顾客1.5元，现在你手头有面值为1.1元、5角和1角的硬币若干，试问如何找钱使得所找的硬币总数最少？策略：优先使用面值大的硬币。

1个1.1元的硬币

4个1角的硬币最优解：

3个5角的硬币贪心策略不一定总是能够得到最优解！贪心策略从局部最优出发，每次做一个选择，问题规模就减小一些，重复该过程，直到问题解决。贪心策略不一定总是能够得到最优解。信息工程大学算法设计与分析贪心法—基本原理国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版求解最优化问题的过程包含一系列步骤每一步都有多种选择贪心法做出在当前看来最好的选择希望通过局部最优选择达到全局最优

贪心算法总是做出当前最好的选择，不是从整体上考虑问题的最优性，它所做出的选择只是在某种意义上的局部最优选择，所以有时贪心算法的解不一定是整体最优解。对于一个给定的问题，通常有多种贪心选择策略，但不是每种策略都可以得到最优解。因此，选择能产生问题最优解的贪心选择策略是使用贪心法的核心问题。有些问题的贪心选择策略比较直观，有些问题则需要深入分析。适合用贪心法求解的问题一般具有两个重要性质：贪心选择性质（Greedy-choiceproperty）每步所做的贪心选择最终可求得问题的最优解最优子结构性质（Optimalsubstructure）问题的最优解包含子问题的最优解1.证明所求解的问题具有最优子结构性质。2.证明所求解的问题具有贪心选择性质（证明每一步所做的贪心选择最终导致问题的整体最优解）。反之，只需要举出一个反例，就可以说明贪心法不正确。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是它们的共同点。

但对于具有最优子结构的问题：选用贪心法还是动态规划求解?能用动态规划求解的问题是否也能用贪心法求解?

给定n个物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?物品i要么全部装入要么不装。0-1背包问题：与0-1背包问题不同的是，在选择物品i装入背包时，可以选择物品i的一部分xi，不一定要全部装入背包，0≤xi≤1。部分背包问题：选择题。你觉得以下哪种贪心选择策略可以得到部分背包问题的最优解？A.重量轻的物品优先装入B.价值大的物品优先装入C.单位重量价值大的物品优先装入D.以上都不对部分背包问题的贪心选择策略有：1.重量轻优先2.价值大优先3.单位重量价值大优先反例：n=2，c=5，w=(2,5)，v=(2,10)，优先装入物品1，再装入物品2的一部分，得到价值总和为8；而把物品2全部装入背包得到价值10是最优解。反例：n=2，c=5，w=(2,5)，v=(6,10)，优先装入物品2，得到价值10；而先全部装入物品1再装入物品2的一部分，得到价值12是最优解。错误错误该策略综合考虑到物品重量和价值两个因素，可以得到最优解。正确对物品按单位重量价值vi/wi从大到小排序；根据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包；若背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包；依此策略进行下去，直到背包装满为止。贪心法求解部分背包问题的步骤：贪心法求解部分背包问题的代码：voidKnapsack(intn,floatc,float*v,float*w,float*x){knap_sort(n,v,w);/*按单位重量价值从大到小排序*/for(i=1;i<=n;i++)x[i]=0;floatleft=c;/*逐一判断每件物品*/for(i=1;i<=n;i++){if(w[i]>left)break;x[i]=1;left-=w[i];}if(i<=n)x[i]=left/w[i];/*可能有部分装入的物品*/}时间复杂度为O(nlogn)例：c=7,(w1,w2,w3)=(3,4,5),(v1,v2,v3)=(5,6,10)。贪心法得到的最大价值为10，装入物品3。实际最大价值为11，装入物品1和2。贪心法不能正确求解0-1背包问题。原因：无法保证最终能将背包装满，部分闲置的背包空间使背包的单位空间的价值降低。在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再做出最好的选择。由此就出现许多互相重叠的子问题。0-1背包问题可用动态规划求解。贪心法不能正确求解0-1背包问题。动态规划贪心共同点最优子结构性质不同点重叠子问题贪心选择性质求解思路对所有选择比较后决定最优的只考虑一种选择，因而更高效解题过程通常采取自底而上，从小问题推出大问题从大问题逐步求解，不断减少问题规模，直至结束代码结构通常是多重循环通常是排序后一遍扫描贪心法简单、高效。选择正确的贪心选择策略是关键。两个重要性质：最优子结构和贪心选择性质。贪心算法是否产生最优解，需严格证明；反之，要证明某种贪心选择策略是错误的，只需要找出一个反例即可。信息工程大学算法设计与分析贪心法—活动安排问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版活动安排问题：

设有n个活动的集合S={1,2,…,n}，其中每个活动都要求使用同一资源，如教室、会场等，而在同一时间内只有一个活动能使用这个资源。si，fi分别为活动i的开始和结束时间，且si<fi

。活动i与j相容

si

fj或sjfi。求：最大的两两相容的活动集A。

问题的解需要满足以下条件：是n个活动的一个子集任何两个活动都是相容的活动个数最多活动的属性：开始时间、结束时间、持续时间可能的贪心策略：尽早开始，优先安排开始时间早的活动占用时间短，优先安排持续时间短的活动使剩余时间更多，优先安排结束时间早的活动思考：活动安排问题可以用贪心法求解吗？选择题。你觉得以下哪种贪心选择策略可以得到活动安排问题的最优解？A.优先安排开始时间早的活动B.优先安排持续时间短的活动C.优先安排结束时间早的活动D.以上都不对策略1：优先安排开始时间早的活动错误该策略得到的解：活动1最优解：活动2、活动3策略2：

优先安排持续时间短的活动错误该策略得到的解：活动4、5最优解：活动1、2、3策略3：优先安排结束时间早的活动问题：该策略对所有实例都能得到最优解吗？该策略对两个实例都得到了最优解。

时间复杂度为O(nlogn)S={1,2,…,n}是活动集，且f1

…

fn

。

定理：算法GreedySelect执行到第k步，选择k项活动i1=1,i2,…,ik，那么存在最优解A包含i1=1,i2,…,ik。证明：归纳基础：k=1,存在最优解包含活动1。任取最优解A,A中的活动按结束时间递增排列。如果A的第一个活动为j，j

1,由于f1

fj，则有A′=(A

{j})

{1}，且A′也是最优解，并含有活动1。

j…A1…A’归纳步骤：假设命题对k为真，证明对k+1也为真。算法执行到第k步，选择了活动i1=1,i2,…,ik，根据归纳假设存在最优解A包含i1=1,i2,…,ik。

最优解A中剩下的活动子集B来自集合S′={i|i

S,si

fk}，且A={i1,i2,…,ik}B。其中B是S′的最优解。若不然,设S′的最优解为B*,B*的活动比B多，那么B*

{1,i2,…,ik}是S的最优解，且比A的活动多,与A的最优性矛盾。待选集合S′1,i2,…,ik不相容活动集BAB*B={ik+1,…}?将S′看做一个子问题，根据归纳基础，存在S′的最优解B′含有S′中的第一个活动，即ik+1,且|B′|=|B|,于是也是原问题的最优解.待选集合S′1,i2,…,ikBB’ik+1活动安排问题的主要特征：使用一个共享资源，安排尽可能多的活动。在日常生活中这样的应用场景很多，比如给一个教室安排尽可能多的课程、一个会场安排尽量多的会议等。信息工程大学算法设计与分析贪心法—过河问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸，过桥时必须借助灯光照明。独木桥最多能承受两个人，由于只有一盏灯，因此过桥时间等于较慢的那个人单独过桥所需要的时间。给定N个人(2<=N<1000)人单独过桥需要的时间，

请计算最少需要多少时间，他们才能全部到达河左岸。每个人的过河时间从小到大存储在t[i]中，i=0~n-1。按照问题规模从小到大进行分析：当n=1,2时，直接过河；当n=3时，需要两趟；n=3时，用时：t[0]+t[1]+t[2]1.最快的和最慢的(t[2])2.最快的返回(t[0])3.最快的和次慢的(t[1])按照问题规模从小到大进行分析：当n=1,2,3时，容易求解；当n较大时，把若干人送到对岸，再有人把灯拿回来，就可以转换为规模更小的过河问题。基于用时最少的要求，选择过河时间较快的人把灯拿回来。按照问题规模从小到大进行分析。当n=1,2,3时，容易求解；当n≥4时，将过河所需时间最多的两个人送到河对岸，有两种方式：方式一：用最快的逐人送用时：2*t[0]+t[n-1]+t[n-2]方式二：最慢和次慢的一起过河用时：t[0]+2*t[1]+t[n-1]1.最快的和最慢的(t[n-1])2.最快的返回(t[0])3.最快的和次慢的(t[n-2])4.最快的返回(t[0])1.最快的和次快的(t[1])2.最快的返回(t[0])3.最慢的和次慢的(t[n-1])4.次快的返回(t[1])贪心法求解过河问题的步骤：按从小到大的顺序对过河时间排序，存储到数组t中；当n>=4时，比较方式一和方式二的时间，选择用时少的（贪心选择策略），同时n=n-2；重复步骤2，直到人数不足4时，直接求解。sort(t,t+num);/*对过河时间从小到大排序*/voidwork(intn)/*贪心法求解n个人的过河问题*/{if(n==1){ans+=t[0];return;}if(n==2){ans+=t[1];return;}if(n==3){ans+=t[0]+t[1]+t[2];return;}if(n>=4){if((t[1]*2)>=(t[0]+t[n-2]))ans+=t[0]*2+t[n-2]+t[n-1];/*选择方式一*/elseans+=t[1]*2+t[0]+t[n-1];

/*选择方式二*/work(n-2);/*递归调用*/return;}}时间复杂度为O(nlogn)信息工程大学算法设计与分析贪心法—哈夫曼编码国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版二进制编码问题：

给定字符集D={d1,d2,...,dn}，字符出现的频率为{w1,w2,…,wn}，要求为每个字符确定一种由0、1构成的二进制编码方案，使得编码后的文件长度最短。字符编码转换01编码译码转换字符

编码方案：等长编码存在的问题：字符频率不等时，得到的编码总长度可能不是最短的。非等长编码潜在的问题：如00表示E，01表示T，0001表示W，收到的编码是0001，那么这组编码是W还是ET呢？无法区分!!原因是E的编码和W的编码的开始部分（前缀）相同。2.非等长编码：采用非等长的二进制串表示。频度高的字符采用较短的二进制串表示，频度低的字符采用较长的二进制串表示，从而达到缩短报文总长的目的。前缀码：任一字符的编码都不是其它字符编码的前缀。因此，对字符集进行不等长编码，则要求这种不等长编码必须是前缀码。判断题。等长编码一定是前缀码。A.正确B.错误

戴维•哈夫曼提出了利用二叉树构造最优前缀码的方法。相应的二叉树称为哈夫曼树，对应的编码称为哈夫曼编码。设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度li与叶子结点权值wi的乘积的和称为该二叉树的带权路径长度(WeightedPathLength，WPL)。

WPL最小的二叉树称为哈夫曼树。字符出现的频率根结点到字符结点的路径长度二进制编码问题本质上是构造哈夫曼树的问题。基于出现频率越高的字符、编码长度越短的贪心思想，哈夫曼提出了构造哈夫曼树的贪心法，优先选择频率低的字符，以自下而上的方式构造哈夫曼树。哈夫曼树的构造过程：初始时，每个结点作为一棵树，共有n棵树；新建一个结点v，选择具有最低频率的两个根结点作为结点v的左、右孩子，形成一棵树，v的权值为其左、右孩子的权值之和；重复步骤2，直到只剩下一棵树为止。选择题。已知n个叶子结点，构造哈夫曼树需要执行（）次合并操作（合并操作指步骤2）。A.nB.n-1C.以上都不对c:14b:15d:17a:38f:6e:101601第一步例子：a:38，b:15，c:14，d:17，f:6，e:10c:14b:15d:17a:38f:6e:10初始化c:14b:15d:17a:38f:6e:101601第二步2901c:14b:152901f:6e:101601d:1733a:3801620110001第五步c:14b:152901f:6e:101601d:1733a:38016201第四步c:14b:152901f:6e:101601d:1733a:3801第三步字符对应的编码：f：1100e：1101d：111c：100b：101a：0c:14b:152901f:6e:101601d:1733a:3801620110001选择题。下图所示的哈夫曼树，密文“010110111111001101100111”对应的明文是（）。A.abdffecdB.abbdfecdC.以上都不对Huffman(C)/*构建哈夫曼树*/输入：C={x1,x2,…,xn}，n,

f(xi),i=1,2,…,n输出：C’1.复制C到C’中，初始化C’中每个字符的左、右孩子为-1；2.Q

C’;/*用字符频率集构建小根堆*/3.for(i=1;i<=n-1;i++){4.z=Allocate-Node();/*生成新结点z加入C’中*/5.z.left=pop(Q);/*取出Q最小元为z的左儿子*/6.z.right=pop(Q);/*取出Q次小元为z的右儿子*/

7.f(z)=f(x)+f(y);8.push(Q,z);/*将z插入Q*/9.}10.returnC’;时间复杂度为O(nlogn)石子合并问题：有n堆石子排成一排，依次编号为1~n。现要将石子两两合并为一堆，并将新的一堆石子数记为本次合并的代价。计算将n堆石子合并成一堆的最小代价。

结点i的权值wi根结点到结点i的路径长度li

*3465101518合并代价=10+15+18=43=3*1+4*3+6*3+5*2哈夫曼树是WPL最小的二叉树，不仅可以解决最优前缀码问题，还可以解决很多类似的问题。

应用：生活中，把常用的物品放在容易拿到的地方。深入理解WPL的含义是关键。信息工程大学算法设计与分析贪心法--哈夫曼算法的正确性证明国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版定理：Huffman算法对任意规模为n（n2）的字符集C都能得到关于C的最优前缀码的二叉树。

该定理的证明需要两个引理。则T与T’的WPL之差为其中dT(i)为i在T中的层数（i到根的距离）,引理1成立。引理1：设C是字符集，

c

C,f(c)为频率，x,y

C,f(x),f(y)频率最小，那么存在最优二元前缀码使得x,y的编码长度相等，且仅在最后一位不同。f(x)

f(a)f(y)

f(b)a与x交换b与y交换

TT’yabxTbxyaT’证明:设T是C的最优前缀树，且a和b是具有最大深度的两个兄弟字符:引理2：设T是最优二元前缀码所对应的二叉树，

x,y

T,x,y是树叶兄弟，z是x,y的父亲，令T’=T

{x,y},且令z的频率f(z)=f(x)+f(y)，T’是对应于二元前缀码C’=(C

{x,y})

{z}的二叉树，那么WPL(T)=WPL

(T’)+f(x)+f(y)。bczT’0011f(c)f(b)f(x)+f(y)bcxyT000111f(x)f(c)f(y)f(b)z定理：Huffman算法对任意规模为n（n2）的字符集C都能得到关于C的最优前缀码的二叉树。

归纳基础

n=2，字符集C={x1,x2}，Huffman算法得到的编码是0和1，是最优前缀码。归纳步骤

假设Huffman算法对于规模为k的字符集能得到最优前缀码。考虑规模为k+1的字符集C={x1,x2,...,xk+1},其中x1,x2

C是频率最小的两个字符。

令

C’=(C－{x1,x2})

{z}，

f(z)=f(x1)+f(x2)根据归纳假设，Huffman算法得到一棵关于字符集C’、频率f(z)和f(xi)（i=3,4,...,k+1）的最优前缀码的二叉树T’。把x1和x2作为z的儿子附加到T’上，得到树T，那么T是关于字符集C=(C’－{z})

{x1,x2}的最优前缀码的二叉树。

zT’x2x1T

zx1T*x2T*‘

z如若不然，存在更优的树T*。根据引理1，其最深层树叶是x1,

x2，且WPL(T*)<WPL(T)。去掉T*中的x1和x2，根据引理2，所得二叉树T*’满足WPL(T*’)＝WPL(T*)－(f(x1)+f(x2))<WPL(T)－(f(x1)+f(x2))=WPL(T’)与T’是一棵关于C’的最优前缀码的二叉树矛盾。

信息工程大学算法设计与分析贪心法—最小生成树国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版最小生成树(Minimum-costSpanningTree)：设G=(V,E)是无向连通带权图，即一个网络。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。

生成树的性质：包含n个顶点；有且仅有(n-1)条边；任两点都是有路可达的。生成树上各边权的总和称为该生成树的耗费。耗费最小的生成树称为G的最小生成树。1234566515366425

最小生成树有广泛应用。比如建立城市间的通信网络、乡村间的道路连通等问题，最小生成树可以给出最优的建设方案。最小生成树问题的本质：求无向连通带权图的最小连通代价。判断题。对于一个无向连通带权图，最小生成树可能是不唯一的。A.不正确B.正确Prim算法和Kruskal算法都是用贪心思想构造的最小生成树。尽管它们的贪心策略不同，但都利用了最小生成树性质。

uv顶点集U顶点集V-UMST性质证明：（反证法）假设G的任何一棵最小生成树中都不包含边(u,v)。设T是G的一棵最小生成树，但不包含边(u,v)。由于T是树，且是连通的，因此必有一条从u到v的路径，且该路径上必有一条连接两个顶点集U和V-U的边(u',v')，其中u'属于U，v'属于V-U。将边(u,v)加入到T中，得到一个含边(u,v)的回路。当删除边(u',v')时，回路被消除。由此得到另一棵生成树T’，T’和T的区别仅在于用边(u,v)取代了T中的边(u’,v’)。因为(u,v)的权<=(u’,v’)的权，故T‘的权值<=T的权值。因此，T’也是G的最小生成树，并包含边（u,v），与假设矛盾。uu'vv'顶点集U顶点集V-U

1234566515366425123456112345614123456142123456154212345615342①②③④⑤⑥

需要的数据结构：标识顶点i是否属于集合S：使用数组s如何有效地找出满足条件i

S，j

V-S，且权值c[i][j]最小的边(i,j)？

对于V-S中每个顶点j，把S到j权值最小的点i存入parent[j]，权值c[i][j]存入dist[j]，当有新的点加入S时，更新parent[j]和dist[j]。1234566515366425迭代Sjp[2]d[2]p[3]d[3]p[4]d[4]p[5]d[5]p[6]d[6]初始{1}161115—∞—∞1{1,3}335111536342{1,3,6}635116236343{1,3,6,4}435116236344{1,3,6,4,2}235116223345{1,3,6,4,2,5}3511622334Prim算法执行过程中相关数组的变化情况（parent[j]简写为p[j]，dist[j]简写为d[j]）1234561(1)5(4)3(5)4(2)2(3)voidprim(){/*prim算法构建最小生成树*//*初始化*/s[1]=1;s[2~n]=0;forj=2ton ifc[1][j]!=INF{parent[j]=1;dist[j]=c[j][1]；}/*循环n-1次，依次加入点和边*/for(k=1;k<=n-1;k++){/*找出V-S中dist值最小的顶点j*/inttmin=INF;j=-1;fori=2ton if(s[i]==0)&&dist[i]<tmin){tmin=dist[i];j=i;}s[j]=1;/*将j添加到S中*//*依次判断和j相邻且在V-S中的点，判断该边权值是否更小，如果是，则修改parent和dist*/fori=2tonif(s[i]==0)&&dist[i]<c[j][i]){dist[i]=c[j][i];parent[i]=j;}}}时间复杂度：O(n2)最小生成树性质：只要是连接两个集合的权值最小的边，一定在某棵最小生成树中。Kruskal算法基本思想：1.

n个顶点看成n个孤立的连通分支，将所有的边按权值从小到大排序；

2.依次查看每一条边(i,j)，如果i和j分别来自不同的连通分支T1和T2时，就用边(i,j)将T1和T2连接成一个连通分支；3.重复步骤2，直到只剩下一个连通分支时为止。1234561212345611234561534212345612312345665153664251234561423①②③④⑤⑥Kruskal算法中的关键步骤：边按权值从小到大排序逐一判断边的两个邻接点是否在同一个连通分支中，如不是1）合并两个端点所在的分支2）把边加入最小生成树中用并查集高效实现查找元素属于哪个集合合并两个集合Prim算法和Kruskal算法比较：共同点：根据MST性质做贪心选择不同点：Prim算法：不断加点，时间复杂度为O(n2)Kr