计算机常用算法与程序设计教程 第5章 贪心算法

《计算机常用算法与程序设计教程 第5章 贪心算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章贪心算法1常用算法与程序设计主要内容5.1贪心算法概述5.2贪心算法的理论基础5.3删数字问题5.4背包问题5.5覆盖问题5.6图的着色问题5.7遍历问题5.8最小生成树5.9哈夫曼编码2常用算法与程序设计5.1贪心算法概述5.1.1贪心算法有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i个货箱的重量为wi（1≤i≤n），而货船的最大载重量为c，我们的目的是在货船上装入最多的货物。这个问题可以作为最优化问题进行描述：设存在一组变量xi，其可能取值为0或1。如xi为0，则货箱i将不被装上船；如xi为1

2、，则货箱i将被装上船。我们的目的是找到一组xi，使它满足限制条件ni=∑wixi≤c且xi∈[0,1],1≤i≤n。相应的优化函数是ni=∑wixi取极值。满足限制条件的每一组xi都是一个可行解，能使ni=∑wixi取得极大值的方案是最优解。3常用算法与程序设计贪心算法（也称贪心策略）总是作出在当前看来是最好的选择。如上面的找硬币问题本身具有最优子结构性质，它可以用动态规划算法来解。但我们看到，用贪心算法更简单，更直接且解题效率更高。这利用了问题本身的一些特性。贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择，不断把将问题转化

3、为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。从求解效率来说，贪心算法比动态规划更高，且不存在空间限制的影响。另外，对一些NP完全问题或规模很大的优化问题，可通过仿贪心算法能得到很好的近世解，而用动态规划根本无法解。4常用算法与程序设计5.1.2.贪心算法的基本思想贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：(1)可行的：必须满足问题的约束。(2)局部最

4、优：当前所有可能的选择中最佳的局部选择。(3)不可取消:选择一旦做出，在后面的步骤中就无法改变了。贪心算法是通过做一系列的选择来给出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择。这种启发式策略并不总是能产生出最优解。5常用算法与程序设计5.2贪心算法的理论基础“矩阵胚”理论“矩阵胚”理论是一种能够确定贪心算法何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。定义 矩阵胚是一个序对M=[S，I]，其中S是一个有序非空集合，I是S的一个非空子集，成为S的一个独立子集。6常用算法与程序设计如果M是

5、一个N×M的矩阵的话，即:若M是无向图G的矩阵胚的话，则S为图的边集，I是所有构成森林的一组边的子集。如果对S的每一个元素X（X∈S）赋予一个正的权值W（X），则称矩阵胚M=（S，I）为一个加权矩阵胚。7常用算法与程序设计适宜于用贪心算法来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。矩阵胚理论对于我们判断贪心算法是否适用于某一复杂问题是十分有效的。8常用算法与程序设计对给

6、定的n位高精度正整数,去掉其中k(k1(当

7、然小于n),按上述操作一个一个删除。删除一个达到最大后,再从头即从串首开始,删除第2个,依此分解为k次完成。若删除不到k个后已无左边小于右边的增序,则停止删除操作,打印剩下串的左边n-k个数字即可(相当于删除了若干个最右边的数字)。下面我们给出采用贪心算法的删数字问题的部分c语言代码：10常用算法与程序设计while(k>x&&m==0){i=i+1;if(a[i-1]

8、/i=0;/*从头开始查