[第四章贪心算法.pptVIP

* OUTLINE 1、背包问题 2、贪心算法的基本要素 3、贪心和DP的区别 4、单源点最短路径问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 第4章 贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 4.1 背包问题---问题描述 已知有n种物品和一个可容纳c重量的背包，每种物品i的重量为wi。假定物品i的一部分放入背包会得到vixi的效益。其中0≤xi≤1,vi0 . 采用怎样的装包方法才会使装入背包物品的总效益最大呢？即求解 (4.2.1) (4.2.2) (4.2.3) 其中（4.2.1）是目标函数，（4.2.2）及（4.2.3）是约束条件。满足约束条件的任一集合(x1,…,xn) 一个可行解，使目标函数取最大值的可行解是最优解。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 例4.4 考虑下列情况下的背包问题: n＝3,c＝20, (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) 其中的四个可行解是 ①（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 先检验这四个为可行解*,即满足约束条件(4.2.2),(4.2.3).再比较目标函数值,∑vixi .知④组解效益值最大.该组解是背包问题的最优解。 4.1 背包问题的实例 问题求解策略： 度量标准的选择：三种不同的选择 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 可行解有无穷多. * （1）取目标函数作为量度标准，即每次选择利润最大的物品装包，使背包获得最大可能的效益值增量。在此量度标准下贪心方法就是按效益值的非增次序，将物品一一装包，直到某一i物品放不下时，取一种能获得最大增量的物品，将它（或其一部分）放入背包，而使最后一次装包也符合量度标准的要求，如：还剩下两个单位的空间，而背包外还有两种物品。 ， 则用i比j好，∵装入A，Vi=4 ;而装入B,Vj=3 。 对例 4.4的数据使用按效益值的非增次序的选择策略. 例4.4 n＝3,c＝20, 背包剩：C－18＝2；物品2有次大效益值 (V2=24 )但w2=15,背包装不下物品2。使用 x2=2/15,刚好装满背包 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 按此选择策略,得②即(1, 2/15, 0),∑vixi=28.2 .此解是一个次优解。显然，按物品效益值的非增次序装包不能得最优解。 原因：背包可用容量消耗过快。 （2）以容量作为量度。即按物品重量的非降次序将物品装包。如例4.4中的解③（让背包尽可能慢被消耗） 排序 :