算法设计与分析实用教程杨克昌 第7章 贪心算法

《算法设计与分析实用教程杨克昌 第7章 贪心算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求了解贪心算法的概念与贪心策略的选择掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例本章重点根据案例的实际选择与确定贪心策略第7章贪心算法7.1贪心算法概述7.1.1贪心算法的概念(1)贪心算法又称贪婪算法，是一种着眼局部的简单而适应范围有限的优化策略。(2)当一个问题具有最优子结构性质时，贪心算法有时比动态规划法求解更为简单有效。(3)贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是做一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算

2、法并不从整体最优考虑，它所作出的选择只是局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。（4）贪心策略的选择贪心算法没有固定的算法框架，算法设计的关键在于贪心策略的选择与确定。贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。应用贪心算法所做的每一步选择都必须满足：1）可行的：必须满足问题的约束条件。2）局部最优：当前所有可能的选择中选择使局部最优的决策。3）不可取消：选择一旦做出，在后面的步骤中无法改变。贪心算法是通过做一

3、系列的选择来求出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择，这种启发式策略并不总能产生出最优解。贪心算法的理论基础为拟阵，是组合优化与图论的重要内容。矩阵胚（matroid）又称为拟阵，是一个满足以下交换性质的特殊子集系统：判断一个子集系统是不是矩阵胚常应用以下性质：定理1一个子集系统是矩阵胚当且仅当所有极大独立子集具有相同的基数。例如,若S是一个矩阵中行向量集合，I是S的线性独立子集族，则（S,I）是矩阵胚。定理2子集系统优化问题的贪心算法正确，当且仅当该子集系统是一个矩阵胚。7

4、.1.2贪心算法的理论基础7.2背包问题7.2.1可拆背包问题//已对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];3.贪心算法描述7.3删数字问题案例提出：在给定的n个数字的数字串中，删除其中k(k

5、下的数字按原次序组成一个新的正整数。请确定删除方案，使得剩下的数字组成的新正整数最大。例如在整数79502867154829179316中删除8个数字后，所得最大整数为多大？操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。这就是所要选取的贪心策略。每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。选择这样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。当k=1时，在n位整数中删除哪一个数字能达到最

6、大？从左到右每相邻的两个数字比较：若出现增，即左边数字小于右边数字，则删除左边的小数字。若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。1.贪心算法设计要点例如，在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！往后推，“6”与“2”比较，因6>2，为减，“6”不能删；再往后推，“2”与“1”比较，因2>1,为减，“2”不能删；继续往后推

7、，“1”与“9”比较，因1<9，出现增，则删除左边的小数字“1”。当k>1（当然小于n），按上述操作,每一次操作从串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。每次操作删除一个数字后，后面的数字向前移位。因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边n−k个数字即可（相当于删除了余下的最右边若干个小数字）。printf("删除数字个数:");scanf("%d",&k);i=0;m=0;x=0;while(k>x

8、&&m==0){i=i+1;if(a[i-1]