第4章 贪心算法

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

1、第4章贪心算法4.1什么是贪心法4.2贪心法的典型示例本章小结4.1什么是贪心法4.1.1复杂问题的求解方法4.1.2贪心法的设计思想4.2.3几个例子4.2.4小结4.1.1复杂问题的求解典型方法分治法将复杂问题分成若干个相互独立的子问题，通过求解子问题，并将子问题的解合并得到原问题的解。动态规划法将一个复杂问题分解为若干个相互重叠的子问题，通过求解子问题形成一系列决策得到原问题的解。4.1.1复杂问题的求解典型方法贪心法（GreedyMethod）将一个复杂问题分解为一系列较为简单的局部最优选择，每一个

2、选择都是对当前解的一个扩展，直到获得问题的完整解。搜索法4.1.2贪心法的设计思想基本思想将问题的求解过程看作是一系列选择，每次选择都是当前状态下的最好选择(局部最优解)。每作一次选择后，所求问题会简化为一个规模更小的子问题，从而通过每一步的最优解逐步达到整体的最优解。4.1.2贪心法的设计思想特点贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之：贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。4.2.

3、3几个例子例1：数字三角形问题例2：渴婴问题例3：找零钱问题例1：数字三角形问题数字三角形问题穷举法动态规划法89：13-11-26-15-24贪心法63：13-11-12-14-131311872612141567131211824例2：渴婴问题问题描述已知：饮料类型：n饮料满意度：s1,s2,…,si,…,sn饮料总量：a1,a2,…,ai,…,an需求：t问：需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求，而且能达到最大的满意程度呢？例2：渴婴问题问题分析：令：xi为婴儿将要饮用的第i种饮料的量

4、则：需要解决的问题是找到一组实数xi（1≤i≤n）例2：渴婴问题解决方案：分步获取饮料，每次喝一种饮料，且需要考虑选用哪种饮料；根据这种思想，利用如下的贪心准则：从余下的饮料中，选择满意度最高的饮料，直到达到解渴的需要，或者全部饮料被喝完为止。例3：找零钱问题问题描述假如售货员需要找给小孩98元的零钱，售货员手中有1、2、5、10、20、50元的零钱若干。在小孩的催促下，售货员想尽快将钱找给小孩。分析：贪心准则：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱数等于要找的零钱）每次所选择的硬

5、币不应使零钱总数超过最终所需的数目。具体做法：98＝50＋20＋20＋5＋2＋14.1.4小结思想由一系列步骤构成每步满足可行：满足问题的约束条件局部最优：当前状况下的最优解不可取消：一旦作出选择，不可更改求解问题的类型局部最优导致全局最优（最优解）局部最优接近全局最优（近似解），但速度极快优点求解速度快，时间复杂性有较低的阶。4.1.4小结贪心法的基本要素:具备贪心选择性质和最优子结构性质的最优化问题。整体的最优解可通过一系列局部最优解达到。每次的选择可以依赖以前作出的选择,但不能依赖于后面的选择。问题的

6、整体最优解中包含着它的子问题的最优解.4.2贪心法的典型应用组合问题中的贪心法图问题中的贪心法其他问题应用专题一组合问题中的贪心法例1：活动安排问题例2：最优装载问题例3：0－1背包问题例4：背包问题贪心法与动态规划法的异同点例5：多机调度问题例1：活动安排问题问题提出：n个活动的集合E={1,2,…,n}每个活动i要求使用资源的时间：[si,fi)活动i与活动j是相容的：若区间[si,fi)与区间[sj,fj)不相交，称活动i与活动j是相容的。活动安排问题：在所给的活动集合中选出最大的相容活动子集合。即：

7、要求高效地安排一系列争用某一公共资源的活动。例1：活动安排问题分析：安排活动时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的时间，从而达到安排最多活动的目标。贪心准则在未安排的活动中挑选结束时间最早的活动安排。将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结束时间非减排列：f1f2…fn。例1：活动安排问题例如：12345678910112456137i1234567s[i]1345556f[i]45678910例1：活动安排问题算法描述：intgr

8、eedySelector(ints[],intf[],boola[]){a[1]=true;intj=1,count=1;for(inti=2;i<=n;i++)if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;returncount;}例1：活动安排问题算法时间分析：算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需