第四章 贪心算法.ppt

* OUTLINE 1、背包问题 2、贪心算法的基本要素 3、贪心和DP的区别 4、单源点最短路径问题 * 第4章 贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 * 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) 一个可行解，使目标函数取最大值的可行解是最优解。 * 例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 背包问题的实例 问题求解策略： 度量标准的选择：三种不同的选择 可行解有无穷多. * （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,刚好装满背包 * 按此选择策略,得②即(1, 2/15, 0),∑vixi=28.2 .此解是一个次优解。显然，按物品效益值的非增次序装包不能得最优解。 原因：背包可用容量消耗过快。 （2）以容量作为量度。即按物品重量的非降次序将物品装包。如例4.4中的解③（让背包尽可能慢被消耗） 排序 : (w3,w2,w1)= (10,15,18) V3=15,x3=1,w3=10,背包剩余C－10＝10;物品2有次大重量(w2＝15),但包装不下。使用x2＝2/3，刚好装满背包且物品2装入2/3与物品1装入5/9的容量均为10个单位。但前者的效益值24×2/3=16 后者效益值＝25×5/9≈14，但③ ∑vixi=31, 解（0，2/3，1) 仍是一个次优解 。 原因：容量慢慢消耗，但效益值未能迅速增大。 * （3）效益值的增长速率和容量的消耗速率间取平衡的量度标准。即以单位效益为量度，使物品装入次序按比值的非增次序排列，应用于例4.4的数据，得解④:（0, 1, 1/2）,∑vixi= 31.5 ,∑wixi=20. 为例4.4背包问题的最优解. 选取最优的量度标准实为用贪心方法求解问题的核心. 直接将目标函数作为量度标准也不一定能够得到问题的最优解 贪心解 最优解 * 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 用算法KNAPSACK可实现求背包问题的