第 7 章 贪心算法 了解贪心算法的概念与贪心算法设计要领 掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例

Presentation on theme: "第 7 章 贪心算法 了解贪心算法的概念与贪心算法设计要领 掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例"— Presentation transcript:

1 第 7 章 贪心算法 了解贪心算法的概念与贪心算法设计要领 掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例
第 7 章 贪心算法 教学要求 了解贪心算法的概念与贪心算法设计要领 掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例 本章重点 根据案例的实际选择与确定贪心策略

2 贪心算法概述 1. 贪心算法的概念 (1) 贪心算法（Greedy Algorithm）又称贪婪算法，是一种着眼局部的简单而适应范围有限的优化策略。 (2) 当一个问题具有最优子结构性质时，贪心算法有时比动态规划法求解更为简单有效。 (3) 贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是做一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。

3 2. 贪心策略的选择 贪心算法没有固定的算法框架，算法设计的关键在于贪心策略的选择与确定。 贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。 应用贪心算法所做的每一步选择都必须满足： （1）可行的：必须满足问题的约束条件。 （2）局部最优：当前所有可能的选择中选择使局部最优的决策。 （3）不可取消：选择一旦做出，在后面的步骤中无法改变。 贪心算法是通过做一系列的选择来求出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择，这种启发式策略并不总能产生出最优解。

4 3. 贪心算法的理论基础 贪心算法的理论基础为拟阵，是组合优化与图论的重要内容。 若M是无向图G的拟阵，则S为图的边集，I是所有构成森林的一组边的子集。 如果对S的每一个元素X(X∈S)赋予一个正的权值W(X)，则称拟阵M=(S,I)为一个加权拟阵。 适宜于用贪心算法来求解的许多问题都可以归结为在加权拟阵中找一个具有最大权值的独立子集的问题，即给定一个加权拟阵M=(S,I)，若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。 拟阵理论是一种能够确定贪心算法何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。

5 7.2 删数字问题 案例提出： 在给定的n个数字的数字串中，删除其中k(k<n)个数字后，剩下的数字按原次序组成一个新的正整数。请确定删除方案，使得剩下的数字组成的新正整数最大。 例如在整数 中删除6个数字后，所得最大整数为多大？

6 1. 贪心算法设计要点 操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。
1. 贪心算法设计要点 操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。 在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。这就是所要选取的贪心策略。 每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。选择这样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。 当k=1时，在n位整数中删除哪一个数字能达到最大？从左到右每相邻的两个数字比较：若出现增，即左边数字小于右边数字，则删除左边的小数字。若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。

7 例如，在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？
要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！ 往后推，“6”与“2”比较，因6>2，为减，“6”不能删； 再往后推，“2”与“1”比较，因2>1,为减，“2”不能删 ； 继续往后推，“1”与“9”比较，因1<9，出现增，则删除左边的小数字“1”。 当k>1（当然小于n），按上述操作,每一次操作从串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。每次操作删除一个数字后，后面的数字向前移位。 因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边n−k个数字即可（相当于删除了余下的最右边若干个小数字）。

8 2. 贪心算法描述 printf(" 删除数字个数: ");scanf("%d",&k); i=0;m=0;x=0;
2. 贪心算法描述 printf(" 删除数字个数: ");scanf("%d",&k); i=0;m=0;x=0; while(k>x && m==0) {i=i+1; if(a[i-1]<a[i]) // 两位比较出现递增,删除首数字 {printf("%d, ",a[i-1]); for(j=i-1;j<=n-x-2;j++) a[j]=a[j+1]; x=x+1; i=0; // 从头开始查递增区间 } if(i==n-x-1) m=1; // 已无递增区间,m=1脱离循环 if(x<k) printf("及右边的%d个数字。\n",k-x); printf("\n 删除后所得最大数 ");

9 3. 贪心算法改进 1）以上贪心删数字算法每删除一个数字a[i-1]，赋值i=0，即必须从头开始查找递增区间。其实此时只需从a[i-2]开始查找递增区间即可，因为先前的操作能够保证a[i-2]及之前的数字不是递增区间。 2）以上贪心删数字算法每删除一个数字a[i-1]，必须逐一把其后的数字往前移动一位，如果n及k相当大，移动过程花费较大。其实每删除数字后，并不一定需要移动数字的位置，只对所删除数位赋标记值-1即可，代表该位置的数字已经删除。同时，查找递增区间时跳过该数位。

10 7.3 埃及分数式 案例提出： “埃及分数”为分子为1的分数。
7.3 埃及分数式 案例提出： “埃及分数”为分子为1的分数。 人们研究较多且颇感兴趣的问题是:把一个给定的分数转化为若干个不相同的埃及分数之和，约定埃及分数的分母不能与给定分数的分母相同。常把分解式中埃及分数的个数最少，或在个数相同时埃及分数中最大分母为最小的分解式称为最优分解式。 对把给定分数分解为埃及分数之和，或对已有的埃及分数式进行优化，往往是一个繁琐艰辛的过程。 例如，对3/11，可分解为: 3/11=1/5+1/15+1/165 试寻求分数3/11新的埃及分数式。

11 1．贪心算法设计要点

12 2．贪心算法设计步骤

13 3．贪心选择范围的扩展 以上贪心选择时，每一步都选比本分数小的最大埃及分数。这样尽管快速，但因为太严格可能会失去一些构建时机，或者可能根本找不到埃及分数式。 试把埃及分数贪心选择的环境适当放宽，选择范围适当扩大，即埃及分数的分母由以上贪心选择最小分母c=int(b/a)+1，扩展至c=int(b/a)+d，这里d为放宽尺度1,…,5等。必要时可把该尺度作扩大或缩小调整。

14 7.4 可拆背包问题

15

16 3. 贪心算法描述 // 已对n件物品按单位重量的效益降序排序 cw=c;s=0; // cw为背包还可装的重量
3. 贪心算法描述 // 已对n件物品按单位重量的效益降序排序 cw=c;s=0; // cw为背包还可装的重量 for(i=1;i<=n;i++) {if(w[i]>cw) break; x[i]=1.0; // 若w(i)<=cw,整体装入 cw=cw−w[i]; s=s+p[i]; } x[i]=(float)(cw/w[i]); // 若w(i)>cw,装入一部分) s=s+p[i]*x[i];

17 7.5 数列操作与极差 数列操作 案例提出： 给定一个由n个正整数组成的数列，对数列进行一次操作：去除其中两项a、b，然后添加一项a×b+1。每操作一次数列减少一项，经n−1次操作后该数列只剩一个数。 试求在n-1次操作后最后得数的最大值。

18 1. 贪心算法设计 要点 设数列有3项x，y，z (x≤y≤z)，由 (x×y+1)×z+1 ≥ (x×z+1)×y+1 ≥ (y×z+1)×x+1 可知选取数列中最小的2项操作，可使积最大。 采用贪心算法，当数列中有3项以上时，为使最后所得数最大，每次选择去掉最小的2项操作。 设置a数组存储数列各项，同时对n项进行升序排列。

19 为了得到最大值，设置控制n-1次操作的k（1——n-1）循环。每次操作对最小的前2 项a[k]、a[k+1]实施操作：
x=a[k];y=a[k+1];a[k+1]=x*y+1; 操作后，应用逐项比较对a[k+1]，…，a[n]进行升序排列，为下一次操作做准备。 最后所得a[n]即为所求的数列操作的最大值。 因应用逐项比较进行排列，其时间复杂度为O(n^2)，因而数列操作的贪心设计的时间复杂度为O(n^3)。

20 2. 贪心算法设计 描述 // 先行对原始数据a数组升序排序 for(k=1;k<=n-1;k++) // 共操作n-1次
2. 贪心算法设计 描述 // 先行对原始数据a数组升序排序 for(k=1;k<=n-1;k++) // 共操作n-1次 { x=a[k];y=a[k+1];a[k+1]=x*y+1; // 实施一次操作 for(i=k+1;i<=n-1;i++) // 操作后升序排列 for(j=i+1;j<=n;j++) if(a[i]>a[j]) { h=a[i];a[i]=a[j];a[j]=h;} } printf("\n 最大值为：%ld \n",a[n]);

21 3. 贪心算法设计 优化 按贪心算法，每次操作只对最小的两项进行操作，因而无须对整个数列排序。我们只要把实施排序的2重循环
3. 贪心算法设计 优化 按贪心算法，每次操作只对最小的两项进行操作，因而无须对整个数列排序。我们只要把实施排序的2重循环 for(i=k+1;i<=n-1;i++) for(j=i+1;j<=n;j++) 改进为: for(i=k+1;i<=k+2;i++) 这样，把原排序的时间复杂度O(n^2)降低为O(n)，于是整个数列操作的时间复杂度降低至O(n^2)。

22 7.6 哈夫曼树及其应用 哈夫曼树 设二叉树共有n个端点，从二叉树第k个端点到树的根结点的路径长度l(k)为该端结点（或叶子）的祖先数，即该叶子的层数减1。同时，每一个结点都带一个权（实数），第k个端点所带权为w(k)。定义各个端结点的路径长l(k)与该点的权w(k)的乘积之和为该二叉树的带权路径长，即 对n个权值w(1),w(2),…,w(n)，构造出所有由n个分别带这些权值的叶结点组成的二叉树，其中带权路径长wpl最小的二叉树称为哈夫曼树。

23 例如，给出5个权值{5,4,7,2,8},可生成多棵二叉树，下图所示为其中的3棵：
它们的带权路径长wpl分别为 (a) wpl=7×3+2×3+4×2+5×2+8×2=61 (b) wpl=5×3+2×3+8×2+4×2+7×2=59 (c) wpl=2×3+4×3+5×2+7×2+8×2=58 比较所有的二叉树，其中图(c)的wpl最小，即为对应权{5,4,7,2,8}的哈夫曼树。

24 1. 哈夫曼算法 哈夫曼给出一个贪心策略的算法，称为哈夫曼算法。
1. 哈夫曼算法 哈夫曼给出一个贪心策略的算法，称为哈夫曼算法。 1） 根据给定的n个权值{w(1),w(2),…,w(n)}构成n棵二叉树的森林F=(T1,…,Tn)。其中每棵二叉树中只有一个带权为w(k)的根结点，其左右子树为空。 2） 在F中选取两棵结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上结点权值之和。 3） 在F中删除这两棵树，并把新得的二叉树加入F中。 4） 重复以上 2），3），直到F只含一棵树为止。这棵树即为哈夫曼树。

25

26 1. 哈夫曼算法要点 1） 首先，对给定的n个权值作升序排列。
1. 哈夫曼算法要点 1） 首先，对给定的n个权值作升序排列。 2） 设置n-1次操作的k（1——n-1）循环，在第k次操作中，由两个最小权值叶结点生成一个新结点： x=w[2*k-1]; y=w[2*k]; w[n+k]=x+y; lc[n+k]=x; rc[n+k]=y; 3） 新结点参与排序，为下一次操作做准备。 考虑到每一次排序可能改变w数组元素顺序，设置u数组，每次所得新结点，其数据传送给u数组，最后输出时不是按已改变次序的w数组，而是按u数组输出。 4） 为具体画出哈夫曼树提供方便，输出展示每一个结点的左右子结点的表。

27 2. 哈夫曼算法描述 for(k=1;k<=n-1;k++) // 实施操作n-1次 {x=w[2*k-1]; y=w[2*k];
2. 哈夫曼算法描述 for(k=1;k<=n-1;k++) // 实施操作n-1次 {x=w[2*k-1]; y=w[2*k]; w[n+k]=x+y; s=s+w[n+k]; z=w[n+k]; u[n+k]=w[n+k]; printf("\n 第%d次操作后为:",k); for(i=2*k+1;i<=2*k+2;i++) // 操作后找出最小的2项 for(j=i+1;j<=n+k;j++) if(w[i]>w[j]) {h=w[i];w[i]=w[j];w[j]=h;} for(j=2*k+1;j<=n+k;j++) // 输出第k次操作结果 { printf(" %d",w[j]); if(w[j]==z) printf("(%d+%d)",x,y); }} printf("\n 最小带权路径长为：%d ",s);

28 7.7 贪心算法应用小结 比较动态规划与贪心算法都是求解最优化问题： 1. 着眼点不同 动态规划算法着眼全局，而贪心算法着眼局部。
7.7 贪心算法应用小结 比较动态规划与贪心算法都是求解最优化问题： 1. 着眼点不同 动态规划算法着眼全局，而贪心算法着眼局部。 2. 求解的结果可能不同 动态规划算法求解结果总是最优的，贪心算法对大多数优化问题能得到最优解，但有时并不能求得最优解。 3. 求解效率上的差异 从求解效率来说，贪心算法比动态规划更高，且一般不存在空间限制的影响。 4. 求解范围上的差异 应用贪心算法有时可简化一些构造性问题。

29 第7章 作业 第7章上机 习题7: 1, 2, 3, 4, 5 （1） 上机通过本章删数字、埃及分数式、可拆背包与数列操作问题等典型案例；
第7章 作业 习题7: 1, 2, 3, 4, 5 第7章上机 （1） 上机通过本章删数字、埃及分数式、可拆背包与数列操作问题等典型案例； （2） 上机通过习题7-4,7-5； （3） 分组讨论并上机通过哈夫曼树与哈夫曼编码等案例。

30 欢迎大家提出教学建议 返回