算法设计与分析第5章贪心算法

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

1、第5章贪心算法5.1算法概述5.2背包问题5.3带有期限的作业排序5.4最优归并模式5.5哈夫曼编码5.6最小生成树5.7单源点最短路径顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。5.1算法概述贪心算法采用时逐步构

2、造最优解得方法在每个阶段，都在一定的标准下作出一个看上去最优的决策。决策一旦作出，就不可更改。作出这个局部最优决策所依照的标准称为贪心准则贪心算法的特点：1在当前状态下一旦选定一个分量，就不再重试其他的可行性；2它并不从整体最优上作出考虑，它的选择只是在贪心准则下的局部最优选择5.1.1贪心选择性质在求解一个问题的过程中，如果每一个阶段都是当前状态下的最优选择，即局部最优选择，并且最终能够求得问题的整体最优解5.1.2最优子结构性质当一个问题的最优解包括了这个问题的子问题的最优解时，就说这个问题具有最优子问题5.1.3活动安排问题设总

3、共有n项活动(1,2,…,n),并且所有的活动都需要使用同一个会场，而且任意两个活动不能同时使用这个会场。设活动i占用会场的时间时[bi,ei),其中bi=e[j]then{x[i]trueji;}else{x

4、[i]false;}14例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314算法greedySelector的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。假设x是活动安排问题的一个最优解，并且选人x中的活动也是按照其结束的时间非减序排列的，设x中的第一个活动是i当i=1时，x活动就是以贪心选择开始的最优解如果i>1,那么设

5、一个新解x1=x-{i}∪{1}X2=x1-{1}假设此子问题中可以找到另一个解y1,它比x2包含更多的活动，那么将活动1加到y1后就得到整个问题的一个最优解，与假设x是一个最优解想矛盾。5.2背包问题已知一个可容纳重量为C的背包以及n种物品，其中第i件物品的重量为wi,每件物品的效益是pi(pi>0).假设将第i件物品的一部分yi(0<=yi<=1)放入背包，则得到的效益是piyi背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构性

6、质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。Knapsack(ElemtypeWp[n],Elemtypew[n],floaty[n],ElemtypeWC,intn)1fori1ton2doy[i]0;3cuC;4fori1ton5do{6ifw[i]>cubreak;7theny[i]1;8cucu-w[i];9}10ifi<=n11theny[i]cu/w[i]设y[n]是Knapsack算法得出的向量解1如果任意的yi=1,那么这个解肯定是问题的最优解2否则，设j是yi<>1

7、的最小下标。可知1<=iyi的最小下标值，那么（1）假设kyk,所以xkyk,那么很明显【wixi>C,不符合约束条件。所以，xkj,则【wixi>C,这也是不

8、可能的有以上分析可知xk