第4章-贪心算法PPT课件.ppt

第4章 贪心算法;贪心算法;; 在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。 ;贪心算法的设计思路;贪心算法框架;4.1 贪心算法的基本要素;2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。;3.贪心算法与动态规划算法的差异 共同点：求解的问题都具有最优子结构性质 差异点：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。 ;0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包最大承载重量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?;0-1背包与背包问题都具有最优子结构;0-1背包问题不具有贪心选择性质。原因是无法保证能够将背包装满，而所剩空间将会降低总价值。 背包问题具有贪心选择性质。;0-1背包问题不具有贪心选择特性;背包问题具有贪心选择特性;用贪心算法解背包问题的基本步骤： 1.计算每种物品单位重量的价值Vi/Wi； 2.按照单位重量的价值从高到低的顺序排序； 3.依据贪心选择策略，按照单位价值从高到低的顺序，依次将尽可能多的物品装入背包中。 直到背包装满为止。 是否可以将物品装入背包的条件是： 有空间 ;背包问题的贪心算法;背包问题的贪心算法;4.2 活动安排问题;各活动占用资源情况;（1）活动安排具有最优子结构性质;令子问题Sij≠? 且a1为子问题Sij中具有最早完成时间的任务，则a1一定包含在子问题Sij中某个任务相互兼容的最大子集中。 结论：具有贪心选择特性。;证明： 假设子问题Sij的最优解为Aij，其中的任务按照完成??间由小到大排列；且第一个任务为ak。如果ak = a1，成立。 如果ak ≠a1 ，由于a1完成时间较ak早，所以，可以将ak去掉，换成a1，仍然相容，所含任务数量一样。 ;活动安排问题举例;图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。;i;解活动安排问题的贪心算法 int greedySelector(int s[], int f[], boolean a[],int n) { a[1]=true; // 初始化 int j = 1, count = 1; for (int i = 2; i = n; i++) { // 贪心选择 if (s[i] = f[j]) { a[i] = true; j = i; count++; } else a[i] = false; } return count; };假设输入的活动以其完成时间的非减序排列，则算法greedySelector总选择最早完成时间的相容活动加入集合A中。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。 ;4.3 最优装载;最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。 ;(1)最优子结构的性质;(2)贪心选择性质;最优装载贪心算法;;4.4 单源最短路径;v0?v1 :无 v0?v2:10 v0 ?v4 ?v3:50 v0 ?v4:30 v0 ?v4 ?v3 ?v5:60;（1）Dijkstra算法;Dijkstra算法基本过程;Dijkstra算法基本过程;Dijkstra算法的迭代过程;算法;（2）Dijkstra算法具有最优子结构性质;;;（3） Dijkstra算法具有贪心选择性质;计算复杂性;4.5 哈夫曼编码; 哈夫曼编码广泛应用于数据文件压缩中。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较