信奥_贪心算法基础.pptVIP

* 信息学奥林匹克联赛 NOIP 基础算法 贪心算法 贪心算法 贪心算法 需要勇气和智慧的算法 NOIP 基础算法 培训 浙江 新昌信奥培训 QQ:xcxddn@ 例1 最简单的贪心：找零钱 找零钱方法就是一种贪心算法 贪心策略：先找大额的 例如：找80元， 找50， 余30 再找20， 余10 再找10， 余0 共计3 张零钞 在现有币值的情况下，上述算法显然是对的。 问题：假如有40元币值的呢？上述算法正确的条件是什么？ 概念 贪心算法是：指从问题的初始状态出发，向给定的目标递推, 通过若干次当时最佳的贪心选择而得出最优值(或较优解)的一种解题方法。 其实，从“贪心算法”一词我们便可以看出，贪心算法总是作出在当前看来是最优的选择，也就是说贪心算法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解（是否是全局最优，需要证明） 。  贪心算法是一种思想，不是简单的算法。 贪心策略的特点 贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点： 1、贪心选择性质： 所谓贪心选择性质是指应用同一规则，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。 2、局部最优解： 由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解的不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，但贪心策略比动态规划时间效率更高且占用内存更少，编写程序更简单。 贪心算法的基本步骤 1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模，最终覆盖全部范围或规模。 3、将所有部分解综合起来，得到问题的最终解。 贪心算法通常包括排序过程，这是因为贪心选择的对象通常是一个数值递增或递减的有序关系 贪心算法的典型应用 部分背包问题：先按价值/重量比进行排序，优先装入价值/重量比大的物体。 单源最短路径：求从源到所有其他各顶点的最短路长度（Dijkstra算法）。 最小生成树（Prim算法和Kruskal算法）。 例2 背包问题 问题：已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi。假定将物品i的一部分xi放入背包就会得到pixi的价值，这里，0≤xi≤1，pi0。如果这些 物品重量的和大于M，要求所有选中要装入背包的物品总重量不得超过M，而装入背包物品获得的总价值最大。即 0≤xi≤1，pi0，wi0，1≤i≤n 满足约束条件的任一集合(x1，…，xn)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。 例子 n＝3，M=20，P＝(25，24，15) W (18，15，10)。其中的四个可行解是： (x1，x2，x3) ∑wixi ∑pixi ①(1/2，1/3，1/4) 16．5 24．25 ②(1，2/15，0) 20 28．2 ③(0，2/3，1) 20 31 ④(0，1，1/2) 20 31．5 在这四个可行解中，第④个解的总价值最大。这个解是背包问题在这一情况下的最优解。 贪心策略与最优量度表 价值作为量度标准 这是最容易想到的，即每装入一件物品就使背包获得最大可能的价值增量。在这种量度标准下的贪心方法就是按价值的非增次序将物品一件件放到背包中去。如果正在考虑中的物品放不进去，则可只取其一部分来装满背包。第②个解就是这种量度标准下的贪心方法所产生的解，显然它不是最优的。原因在于背包可用容量消耗过快。 容量作为量度 让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放人背包。例3.1的解③就是使用这种贪心策略得到的，它仍不是最优解。其原因在于容量虽然慢慢地被消耗，但价值没能迅速地增加。 价值/重量 为量度 即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位价值。这就需使物品的装人次序按pi/wi比值的非增次序来考虑。解④就是使用这种贪心策略得到的，它是最优解。 部分背包问题的贪心算法 procedure knapsack(p，w，m，x，n) // p(1..n)和w(1..n)分别n件物品的价值和重量 // m是背包的容量大小 x(1..n)是解 排序 :按p(i)/w(i) 从大到小排序的 fillchar(x,sizeof(x),0); //将解