贪心技术课件

贪心技术

5.1贪心策略的思想

5.2背包(Knapsack)问题5.3Huffman编码

5.4多机调度问题的近似解法

5.5单源最短路径的Dijkstra算法

15.1贪心策略的思想5.1.1付款问题

已知：现有的钞票面额和付款额intm[]={5000,2000,1000,500,200,100,50,20,10,5,2,1};intV; （可以由操作者输入）输出：各种币值的钞票数intn[12];使得且最小。算法5.1付款问题的贪心算法Pay

25.1.2铺砖问题

有若干不同规格的砖，要铺满一块平台，总是希望用较少的砖。例如，有三种规格的砖：2×2、0.8×0.8、0.1×0.1，要铺满2.5×2.5(m2)的平面。采用贪心策略，需一块2×2的大砖及25×5+20×5=225块0.1×0.1小砖。显然这不是最优解，用9块0.8×0.8的中砖加上4块0.1×0.1的小砖就可以了，需58块，小于贪心法的结果226块。5.1.3贪心算法的基本思想

贪心算法把一个整体最优问题分解为一系列的最优选择问题，但结果一般为近似最优。另一方面，贪心算法一般都比较简单，计算量小。它具有两种性质：贪心选择性质和最优子结构性质。31.

贪心选择（Greedy-choice）性质指求解问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来完成。2.最优子结构（Optimalsubstructure）性质指这样一类问题，对该问题的最优解中，也必须包含着其子问题的最优解。即该问题解的整体最优性依赖于其局部子问题的解的最优性。3.活动安排（ActivitySelection）问题问题：有n种活动(例如报告、会议)的集合A={1,2,…n}，都需要占用某场地（报告厅或会议室），该场地同一时间只能安排一项活动。已知：活动i需要在时间段[Si,fi)占用该场地，其中Si与fi是活动i占用的起始时间和结束时间，且Si<fi（i=1,2,…n）。

4求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。这里的相容（mutuallycompatible）指活动的时间不相重叠。即活动i，j相容，当且仅当时间区间[Si,fi]与[Sj,fj]不相交，即必须有Si≥fj或Sj≥fi成立。思路：如果希望安排尽量多的活动，显然这里的贪心选择可以有两种不同的处理：

·选Si最小的，这样可以增大场地的利用率；·选fi最小的，使得下一个活动可以更早开始。由于活动的占用时间长度没有限制，因此后一选择更合理。因此，为了在每一次选择时取当前可以安排的活动中最早结束的活动，应首先把n项活动按结束时间的先后进行升序排序。即，使f1≤f2≤…≤fn，然后在Si值不小于当前时刻的活动中取fi值最小者。5算法：(1)对活动集A中的活动按fi值排序(胜序)，得到数组S[1..n]，f[1..n]，其中f[1]≤f[2]≤…≤f[n]；(2)集合B={1}；j=1；i=2；//活动1肯定被选(3)if(S[i]>=f[j]){B+={i}；j=i；}(4)i++；if(i<=n)goto(3)；(5)end。实例：设n=11，经过对结束时间按升序排序之后，S[1..n]和f[1..n]的值为：经计算，被选的活动集合B={1,4,8,11}。i1234567891011S[i]130535688213f[i]456789101112131464.讨论(1)正确性：上述算法可转为下面的递推过程：为证明算法的正确性，只需说明活动1肯定包含在最优活动子集B中即可，可以用归纳法证明。1°n=1时，A={1}，B={1}，算法正确；72°设||A||<n时，算法正确；（由此可知，B-{1}是A’的最优活动子集）3°用反证法证明算法对||A||=n时正确：设：又存在最优活动子集B’={k,…}(k>1)且||B’||>||B||。因为f(1)≤f(k)，故B’-{k}也是A’的相容活动子集，且有||B’-{k}||>||B-{1}||，这与假设2°矛盾。▌(2)时间复杂度分析：因为排序过程可以在O(nlogn)时间内完成，而求最优活动子集的过程只需O(n)次比较，因此这个算法的时间复杂度为O(nlogn)。(3)贪心策略设计算法的一般特点

·

算法的设计比较简单；

·

算法一般比较快速；

·

算法的正确性一般不明显，需要论证；如果正确性不能保证，那么它往往可以得到近似最优解。85.2背包(Knapsack)问题1.

问题描述已知：n个物体{1,2,…,n}与一个背包。物体i的重量（或体积）为Wi>0，价值为Pi>0(i=1,2,…,n)，背包容量为M>0。求：n元向量(X1,X2,…Xn)，0≤Xi≤1(i=1,2,…,n)，使得且达到最大。2.

解题思路假定n种物体的总重量大于M。因此，算法的任务是要从n种物体中选择一部分放入背包，以达到总价值最大的目标。9一个简单实例：设：n=3，M=50，W=(W1,W2,W3)=(20,30,10)，P=(P1,P2,P3)=(100,120,60)，其不同装法的总重量如Fig.5.2。10从例子中的数据可以看到应首先选择单价值Pi/Wi最高的物体放入背包，这就是所谓的贪心选择。因此要对物体重新排序，使其单价值为降序，排序结果为：W=(W1,W2,W3)=(10,20,30)，P=(P1,P2,P3)=(60,100,120)。每次从物体集中选择单价最高的物体，如果其重量小于背包所余重量，就可把它放入其中。然后我们就面临了一个最优子问题——它同样是一个背包问题，只不过这时的总容量M减少了，物体集减小了。因此背包问题也明显具有最优子结构性质，我们可以为其设计一个贪心算法。3.

算法Knapsack算法5.2背包算法Knapsack114.算法的正确性实际上是验证问题的贪心选择性质。算法Knapsack的解(X1,X2,…Xn)为(1,1,…,1,Xi,0,0,…0)的形式，且满足，其中0≤Xi≤1，用反证法：证明：设存在解满足且设：k是第一个使的下标，即且；12分两种情形，(1)，故可知，。即，与假设矛盾。(2)a.当Xk=1时，，因为按降序排列，可知(X1,X2,…,Xn)就是最优解。13b.当Xk<1时，不妨假设最优解形式为，若m=k，则，可知m一定大于k。令，对于(X1,…,Xn)，M’的总价值为；对于，M’的总价值为（物体k…m的平均单位价值×M’）。14∵按降序排列，∴物体k…m的平均单位价值<Pk/Wk

，即，与假设矛盾。5.算法的复杂度由于背包的装入过程仅需O(n)阶的时间，故算法Knapsack的时间代价即为排序算法的时间代价O(nlogn)。除排序过程之外，背包装入过程只需个别的工作单元，即额外空间需求为O(1)阶。151.

不等长编码与频率表Huffman编码是一种不等长编码方法，对出现频率较高的字符赋给短码，而对于不常出现的字符则分配长码，这样可以大大缩短文字的总代码长度。假定一个包含100000个字符的数据文件由6种字符组成，这些字符在文件中出现的频率在下表中给出。5.3Huffman编码

ABCDEF频率(千次)4513121695等长码000001010011100101不等长码01011001111101110016用等长码，数据文件总码长为300,000bit；用不等长码，则为

((45×1)+(13+12+16)×3+(9+5)×4)×1000=224,000位。大约可节省码长25%。等长码方案中，字符的平均码长为3，而不等长编码的平均码长为2.24。2.最优前缀编码问题Huffman编码可以节省空间，但必须解决两个问题：如何在二进制序列中划分出各个代码；如何使数据文件中的平均码长最小。第一个问题在等长码中很简单，例如在上例中，单词FACE的等长码序列和不等长码序列分别为：101000010100FACE110001001101FACE前者很容易划分，每次取3位即可，而对于后者就比较困难了，前缀码(Prefixcodes)就是用来解决这个问题的。17前缀码是这样一种字符编码方法，其任一字符的编码都不是其它字符的前缀，前缀码就是一种具有前缀性质的编码方法。前缀码的译码过程因其前缀性质，不会产生二义性。利用Huffman树，可以使得译码过程过程十分方便。Fig5.3给出了前表中两种前缀码的Huffman树。18可以发现，(b)树中的所有内部结点的左右子树的权值（频率和）与(a)树相比，有一个明显的差别:比较平衡。(a)树中6个内部结点的左右频率和之比为： 86:14,58:28，14:0,45:13,12:16,9:5；(b)树中5个内部结点的左右频率和之比为： 45:55,25:30,12:13,14:16,5:9。这种情形与编码的平均码长有关，前缀编码的另一个目标是最优前缀编码。设前缀编码方案由Huffman树T给出，则字符集CS及其频率函数f(c)，c∈CS的最优前缀编码应满足：平均码长最小。3.Huffman编码算法用贪心策略实现Huffman编码算法。设字符集CS和频率表函数f(c)(c∈CS)已知，算法的目标是生成最优前缀码二叉树。19把CS中的每个字符视为一个由一个结点组成的二叉树，其权值为字符的频率值f(c)。因此，在算法的开始，集合Q由CS中的每个字符形成的n个权为f(c)的（单点）二叉树组成。为了使f(c)值最小的字符有最长的代码，每次在集合Q中选择两个权值最小的树合并为一个新的树，以其权值和为新树的权，以新树取代原来的两个树，经过n-1步合并就得到了最优前缀码Huffman树。构造过程可以描述如下：（1）初始化，由n个单点带权树组成集合Q

Q={t(c)|c∈CS,W(t)=f(c)},m=n；（2）贪心选择，从Q中选权值最小的树t1，t2

20（3）合并，生成树t，以t1、t2分别为其左、右子树， 且f(t)=f(t1)+f(t2)，以t取代t1、t2，m--；（4）如果m>1，GOTO（2）；（5）输出Q中的唯一元素，即所求之最优前缀编码树。4.实例仍以前表给出的字符集CS={A,B,C,D,E,F}和频率表为例，执行上述算法。其过程下图所示。2122235.算法的正确性引理5.1

任何最优前缀编码二叉树都是丰满二叉树。丰满二叉树(fullbinarytree)就是每一个内部结点都有两个子结点的二叉树。证明：设存在一个二叉树T对应于CS的最优编码，但T不是丰满的（反证法），从而可知：①最小；②T中有一内部结点x不“丰满”。不失一般性，设它是深度最大，且只有左子结点。分为两种情况：(a)x的左儿子为叶结点y，用叶结点y取代x，其码长减小，得到T’，显然B(T’)<B(T)，与①矛盾。见Fig.5.5。2425(b)x的左儿子y为内部结点，叶结点z为y的后代，把叶结点z移上作为x的右儿子，其码长减小，得到T’’，显然B(T’’)<B(T)，与①矛盾。见Fig.5.6。▌26引理5.1指明，最优前缀编码树必为一丰满二叉树。下面的两个引理分别证明Huffman算法具有贪心选择性质和最优子结构性质。引理5.2

对于前缀编码问题(CS,f)，已知x,y∈CS，f(x),f(y)为{f(c)|c∈CS}中最小者，且f(x)<f(y)。则必存在(CS,f)的一种最优前缀编码，使x,y的码长相同，且仅最后一位不同。证明：设T为问题(CS,f)的最优前缀编码树，由引理5.1知T为丰满二叉树。设p,q∈CS为T的深度最大的一对叶结点，且f(p)≤f(x)，f(q)≤f(y)。由命题假设，f(p)≥f(x)，f(q)≥f(y)。又因p，q结点最深，故有dT(p)≥dT(x)，dT(q)≥dT(y)。在树T中，交换叶点x与叶点p、交换叶点y与叶点q，得到T’，则在T’中有dT’(x)≥dT’(p)，dT’(y)≥dT’(q)。27因此，其中Br是树T与T’中相同部分的和。∴B(T’)≤B(T)，T’也是最优前缀编码树。其中不等式是基于下面的不等式：∴同理，28引理5.3

丰满二叉树T表示问题(CS,f)的最优前缀编码，如果x,y∈CS是T的一对叶结点，且内部结点z是x,y的父结点。则T’=T-{x,y}表示问题(CS’,f)的最优前缀编码，其中，。证明：分两步①树T中，，故有。②设（反证）T’不是(CS’,f)的最优前缀编码，则存在T’’是其最优解，即B(T’’)<B(T’)。修改T’’，令其叶结点z变为内部结点，增加结点x,y（频率为f(x),f(y)）为z的两个子结点，形成树T’’’，T’’’显然为(CS,f)的前缀编码，且有与T的最优性矛盾。29由引理5.1、5.2、5.3可以得到：定理5.1Huffman算法生成问题(CS,f)的最优前缀编码。6.

算法的复杂度分析算法的时间代价显然为O(n2)阶。由于树操作中仅需要相应的指针域，总结点数不超过n，所以空间代价为O(n)阶。301.

多机调度问题已知：n台相同的处理机P1,P2,…,Pn和m(m>n)项独立的作业J1,J2,…Jm，它们分别需要处理时间t1,t2,…tm，每项作业Ji可在任何一台机器Pj上运行，但不可间断、划分。求：设计一种调度方案，即把m项作业分配到n台机器上完成，所需时间最短，其中Ti为处理机Pi完成分配给它的作业处理时间之和。实际上，是把作业集J1,J2,…Jm划分为n个子集，以满足时间最短的要求。5.4多机调度问题的近似解法312.

解多机调度问题的贪心算法为了把m项作业均衡地分配给n台机器。当m≤n时这个问题很简单，只要顺序分下去，其总时间T=max{ti|1≤i≤m}一定是最短时间。而当m>n时，除了最初的n项作业外，其它作业的分配一般总是面临最先完成已分配作业任务的机器，这时的贪心选择就是把耗时最多的作业分配给先空闲的机器，显然这有利于均衡。算法5.3贪心调度算法GreedyScheduling3.

一个实例设n=3，m=9，T{t1..tm}={81,40,26,4,65,98,53,71,15}。32Fig.5.7给出了采用(a)任意分配(b)贪心分配策略的结果，而(c)是该实例的最优解，其总时间分别为176，160，151。4.

算法的复杂度其时间复杂度为O(n2)，空间复杂度为O(n2)。331.

单源最短路径问题对于带权图G=<V,E,W>，与G的一个顶点s∈V，其中V为图的顶点集，E为边集，W为G的边的权函数。例如，Vi,Vj∈V，则eij=<Vi,Vj>∈E，Wij=W<Vi,Vj>表示eij的权值。单源最短路径（Single-sourceshortestpath）问题就是对于带权图G=<V,E,W>及其顶点s∈V，求从s到G的所有顶点的最短路径。图G=<V,E,W>的一条非空路径(path)P由G的至少一条连续边组成。例如，由边<x,V1,>,<V1,V2>,…,<Vk,y>组成，当k=1即y=V1时，P由<x,y>一条边组成。5.5单源最短路径的Dijkstra算法34路径P的权由组成P的所有边的权之和表示，路径的权也称为路长。由顶点x到顶点y的具有最小权值的路径即x到y的最短路径。2.

单源最短路径算法的思路单源最短路径问题求从顶点s到G的所有顶点的最短路径，实际上是求G的一个子图，它是以s为根的图G的支撑树(Spanningtree)T，从s到树的每一结点的路径应为G的最短路径，但T不一定是G的最小支撑树。设d(v)(v∈V)为从结点v到源s的（最短）距离，我们的目标即是要计算d(v)(v∈V)的所有值。为d(v)赋初始值：，结点到其本身视为有一条长度为0的边；，，v是s的邻点；，，v与s不相邻，暂设其距离为∞。35把所有的顶点分为三类：①已确定了到s最短距离的顶点，称为树顶点。在一开始，这一集合中只包含源点s；②与树顶点相邻的顶点，称为相邻顶点。下一个树顶点应在这个集合中选取。在一开始，它包含s的所有邻点；③其它顶点，与树顶点没有边直接相关，也称为无关顶点。在一开始，就是距离暂定为∞的那些顶点。算法运行的目标就是，在G为连通图的条件下，每次从相邻顶点集中选取新的树顶点。树顶点集扩大，同时新的树顶点的邻点从无关顶点集进入相邻顶点集。继续这个进程，直到全部顶点都成为树顶点。36假设源s有三个邻点v1,v2,v3（见Fig5.8），且d(v1)=2，d(v2)=4，d(v3)=7，可以断定d(v1)=2是v1到s的最小距离。从s到v1不可能有其它更短的路。由此可以简单地把选取新的树结点的规则规定为取相邻顶点集中距离函数值最小的顶点。过程可以从下图中看到。373839算法与一般贪心策略不同之处是每次选择了新的树顶点之后原来为顶点所赋的距离函数值需要调整，可有两种情形：①原来在无关顶点集中的顶点从距离∞改变为新的距离值，例如，在Fig5.9(b)中的v4,v5，由初始的∞改变为：d(v5)=W(s,v1)+W(v1,v5)=8，d(v4)=W(s,v1)+W(v1,v4)=6。②原来已在相邻顶点集中的顶点，由于新的树顶点的加入，其到s的距离值也可能缩小。例如在Fig5.9(b)中的v3，原来到s的距离为d(v3)=7，由于v1加入树顶点集，边<v1,v3>也列入考虑范围，这时，d(v3)=min{d(v3),d(v1)+W(v1,v3)}=5。经过调整后的距离d(v)不一定是最终的最短距离，但其中最小者，即当此顶点被选为新的树顶点时，其到源点s的距离值肯定是最短距离。因此，当所有顶点进入树顶点集时，算法的任务也就完成了。403.

Dijkstra算法设G的顶点集为{1,2,…,n}，顶点1为源s，整形数组Prev[]用来记录最短路径，Prev[i]=j表示顶点i的前导顶点为j。W[1..n,1..n]为权矩阵，W[i][j]为边<i,j>(∈E)的权值。算法5.4单源最短路径算法Dijkstra4.

实例：设n=10的图，其权函数如Fig.5.10所示。41425.

算法的正确性正确性证明的关键是，在经过修正之后，每次抽取的最短dist()值即为最短路径值。6.

算法的复杂度算法有两层循环，每一层至多为n次操作，故为O(n2)阶。7.

讨论①单源最短路径问题是针对有向图的。事实上权矩阵在有向图的情形下是非对称的，这不影响算法的运行。②Dijkstra算法是在假定权值为非负的情况下设计的，当允许负权值出现时，情况要复杂些。例如，源点s到达自身的最短距离不一定是0了。③关于最短路径的快速算法的研究还在继续。有人把复杂度由O(n2)阶降至O(m+nlogn)阶（m为边数），还有人设计出了复杂度更低的算法。第五章完4344算法5.1付款问题的贪心算法Payvoid

Pay(intm[],intV){

inti,R,n[12];for(i=0;i<12;i++)n[i]=0;R=V;i=0;while(R>0){if(m[i]<=R){R-=m[i];n[i]++;}

elsei++;}for(i=0;i<12;i++)

输出n[i]个m[i]面值钞票;}

返回45算法5.2背包算法KnapsackvoidKnapsack(intn,floatM,floatW[],floatP,floatX[]){

Sort(n,W,P);

inti;floatm=M;for(i=1;i<=n;i++)X[i]=0;i=1;

while(W[i]<=m){