第四章 贪心方法.ppt

假设有三种硬币，面值分别为1元、5角、1角。这三种硬币各自数量不限。现要找给顾客2元7角钱，问怎样找钱才能使得找给顾客的硬币数量最少？ 贪心方法，就是总是做出在当前看来是最好的选择的一种方法。 贪心方法，就是指在求解问题的整体最优解可以通过一系列的局部最优解得到。局部最优解就是指当前状态下最好的选择。 需要判断是否使用贪心算法能得到最优解。 * 基本概念: 可行解、最优解、约束条件、目标函数 一类问题有n个输入, 而它的解就是这n个输入的某个子集, 而这个子集必须满足某些事先给定的条件即约束条件, 满足约束条件的子集称为该问题的可行解. 一般来说可行解不是唯一的, 为衡量可行解的优劣, 以函数的形式给出一定的标准, 这些函数称为目标函数, 使目标函数取极值(极大或极小)的可行解就称为最优解. * 贪心方法 贪心方法是根据具体的问题, 选取一种量度标准,按此标准对n个输入进行排序, 然后按该顺序一次输入一个量. 如果这个输入量和当前的部分最优解加在一起不能产生一个可行解, 则不把此输入量加入到这个部分解中, 这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。 A(1) A(2) … A(n) 量度标准1 A1(1) … A1(n) Ak(1) … Ak(n) 量度标准2 量度标准k …… A2(1) … A2(n) 可行解1 可行解2 可行解k 次优解 次优解 最优解 用贪心法求解问题的关键是选择能产生最优解的最优量度标准 4.1 一般方法 Procedure GREEDY(A,n) solution?Ф for i?1 to n do x?SELECT(A) if FEASIBLE(solution,x) then solution?UNION(solution,x) endif repeat return (solution) End GREEDY * 按某种最优量度标准从A种选择一个输入赋给x，并从A中除去 判断x是否可以包含在解向量中 将x与解向量合并并修改目标函数 * 问题描述 已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部分xi放入背包就会得到pixi的效益(0≤xi≤1,pi0) ，采用怎样的装包方法会使装入背包物品的总效益为最大？ 问题的形式描述: 极大化 ∑ pixi 0≤xi≤1, pi0 约束条件 ∑ wi xi ≤M wi0, 1≤i≤n 1≤i≤n 1≤i≤n * 背包问题实例 (x1, x2, x3) ∑wi xi ∑pixi ① (1, 2/15, 0) 20 28.2 ② (1, 0, 1/5) 20 28 ③ (0, 2/3, 1) 20 31 ④ (0, 1, 1/2) 20 31.5 其中的4个可行解是： 有3个物品, 即n=3, 背包能容纳的最大重量为20, 即M=20 物品的价值和重量: (p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10) 4.2 背包问题 * 贪心方法的量度标准选择 用贪心策略求解背包问题时首先要选出量度标准 选效益值(即目标函数)为量度标准 该标准使得背包每装入一件物品就获得最大可能的效益值增量 将物品按效益值非增次序排序: (p1,p2,p3)=(25,24,15) 按该次序将物品一件件放到背包中, 先装物品1(效益最大), 即x1=1, w1=18; 2,3都不能全放入，衡量后2的一部分效益增量最大。 x2=2/15; 最后得到总效益值为∑pixi = 25+24*2/15=28.2 这是一个次优解，原因是背包容量消耗过快 4.2 背包问题 * 选容量为量度标准 将物品按重量的非降次序排序: (w3,w2,w1)=(10,15,18) 按该次序将物品放到背包中,让容量尽可能慢地被消耗 先装物品3, 即x3=1, w3=10, p3x3 =15; 再装入物品2, 因约束条件为∑wi xi ≤M=20, 所以物品2只能装入重量为10的一部分, 即x2=10/15=2/3; 最后得到总效益值为∑pixi =15+24*2/3=31 这仍是一个次优解, 原因是容量在慢慢消耗的过程中, 效益值却没有迅速的增加 该标准使得背包每装入一件物品就获得最小可能的容量增量 4.2 背包问题 * 将物品按pi/wi比值的非增次序排序: (p2/w2 , p3/w3 , p1/w1 )=(24/15, 15/10, 25/18) 即每一次装入的物品使它占用的每一单位