第4章_贪心算法-2016-all.ppt

*;学习要点;贪心算法;; 在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。 付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。 ;*;贪心算法的求解过程;贪心算法框架;贪心算法的基本步骤;*;*;*;;;*;*;0-1背包问题不具有贪心选择性质。原因是无法保证能够将背包装满，而所剩空间将会降低总价值。 背包问题具有贪心选择性质。;背包问题具有贪心选择性质： 最优解分析： 设物体1,物体2,…,物体n已按价值重量比的降序排序。 贪心选择性质： 设X={x1,x2,…,xn}是背包问题的一个最优解。 令k=min{i|xi∈0,1≤i≤n}， 若k=1，则X是以贪心算法开始的最优解。 ;*;*;*;*;*;*;*;*;*;证明： 假设子问题Sij的最优解为Aij，其中的任务按照完成时间由小到大排列；且第一个任务为ak。如果ak = a1，成立。 如果ak ≠a1 ，由于a1完成时间较ak早，所以，可以将ak去掉，换成a1，仍然相容，所含任务数量一样。 ;活动安排的贪心选择性质的证明 ?证明如下：设E=｛0，1，2，…，n-1｝为所给的活动集合。由于E中活动安排安结束时间的非减序排列，所以活动0具有最早完成时间。首先证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动0. 设a是所给的活动安排问题的一个最优解，且a中活动也按结束时间非减序排列，a中的第一个活动是活动k。如k=0，则a就是一个以贪心选择开始的最优解。若k0，则我们设b=a-｛k｝∪｛0｝。由于end[0] ≤end[k],且a中活动是互为相容的，故b中的活动也是互为相容的。又由于b中的活动个数与a中活动个数相同，且a是最优的，故b也是最优的。也就是说b是一个以贪心选择活动0开始的最优活动安排。因此，证明了总存在一个以贪心选择开始的最优活动安排方案，也就是算法具有贪心选择性质。 ;*;*;*;*;*;*;*;*;;*;*;;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;;解码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。 二叉树就是一种好的表示方式。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标” 因为树有这样结构特性：任何一个从根到某一树 叶的路径都不是根到其他叶子的路径的一部分） ;代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 其中（a)为固定长度编码的二叉树表示； （b)为变长编码的二叉树表示； ;*;;*;*;*;*;哈夫曼算法的正确性 要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。;贪心选择性质-二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。;f: 5;;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;*;每次选择多条边来创建最小生成树， 选择下一条边的【贪婪准则】： 从剩下的边中选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。 【注意】可从任一顶点开始，往 T中加入一条代价最小的边(u,v)，使T与(u,v)的并仍是一棵树。 ; 已知连通网G=(V,E)，设其最小生成???G’=(U,T);*;*;*;*; 选择n-1条边； 【贪婪准则】 从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。; 按权值递增的次序选择n-1条边，每选一条边，要判断是否构成回路。;*;*;删数问题;*;*;string a;　　　　　　　　//n位数a int k; cinak; //如果k≥n，数字被删完了 If (k = a.size()) a.erase(); else while(k 0) { 　　//寻找最近下降点 　　int i; 　　for (i=0; (ia.size()-1) (a[i] = a[i+1]); ++i); 　　a.erase(i, 1);　　　　//删除xi 　　k- -; } //删除前导数字0 while(a.size() 1 a[0] == 0) 　　a.erase(0, 1); coutaendl;;旅行规划问题;旅行规划问题;旅行规