1、第五章 贪心方法Date5.1 一般方法1. 问题的一般特征问题有 n个输入，问题的解是由这 n个输入的某个 子集 组成，这个子集必须满足某些事先给定的条件。n 约束条件 ：子集必须满足的条件；n 可行解 ：满足约束条件的子集；可行解可能不唯一；n 目标函数 ：用来衡量可行解优劣的标准，一般以函数的形式给出；n 最优解 ：能够使目标函数取极值（极大或极小）的可行解。分类 ：根据描述问题约束条件和目标函数的 数学模型 的特性和问题的求解方法 的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。 最优化问题求解贪心方法 ：一种改进的 分级 的处理方法，可对满足上述特征的某些问题方便地求解。
2、Date例 找零钱 一个小孩买了价值少于 1元的糖，并将 1元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为 25分、 10分、 5分及 1分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。假设需要找给小孩 67分，首先入选的是两枚 25分的硬币，第三枚入选的不能是 25分的硬币，否则将不可行（零钱总数超过 67分），第三枚应选择 10分的硬币，然后是 5分的，最后加入两个 1分的硬币。贪心算法有
3、种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）Date2. 贪心方法的一般策略问题的一般特征：问题的解是由 n个输入的、满足某些事先给定的条件的子集组成。1）一般方法根据题意，选取一种 量度标准 。然后按照这种量度标准对 n个输入 排序 ，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的 部分最优解 加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的 新的部分解 。2）贪心方法这种能够得到某种量度意义下的最优解的 分级处理 方法称为 贪心方法注： 贪心解 最优解 直接将目标函数作为
4、量度标准 也不一定能够得到问题的最优解3）使用贪心策略求解的关键选取能够得到问题最优解的量度标准。Date3. 贪心方法的抽象化控制描述procedure GREEDY(A,n)/A(1:n)包含 n个输入 /solution /将解向量 solution初始化 为 空 /for i1 to n doxSELECT(A) / 按照度量 标 准，从 A中 选择 一个 输 入，其 值赋 予 x并将之从 A中 删 除 /if FEASIBLE(solution,x) then /判定 x是否可以包含在解向量中，即是否能共同构成可行解 /solutionUNION(solution,x) / 将 x和
5、当前的解向量合并成新的解向量，并修改目 标 函数 /endifrepeatreturn(solution)end GREEDYDate5.2 背包问题1.问题的描述已知 n种物品具有重量 (w1,w2, wn)和效益值 (p1,p2, pn) ， 及一个可容纳 M重量的背包；设当物品 i全部或一部分 xi放入背包将得到 pi xi的效益，这里， 0 xi 1, p i 0。问题 ：采用怎样的装包方法才能使装入背包的物品的 总效益最大 ？分析 ： 装入背包的总重量 不能超过 M 如果所有物品的 总重量 不超过 M， 即 M， 则把 所有 的物品都装入背包中将获得最大可能的效益值 如果物品的总重量
6、 超过了 M， 则将有物品不能（全部）装 入背包中。由于 0xi1 ， 所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为 M的若干物品（整个或一部分）目标 ：使装入背包的物品的 总效益 达到 最大 。Date问题的形式描述目标函数 ：约束条件 ：可 行 解 ：满足上述约束条件的 任一集合 (x1,x2, xn) 都是问题的一个可行解 可行解可能为多个。(x1,x2, xn)称为问题的一个 解向量最 优 解 ：能够使目标函数取 最大值 的可行解是问题的最优解 最优解也可能为多个。Date例 5.1 背包问题的实例设， n=3， M=20，(p1,p2,p3) = (25,24,15
7、)， (w1,w2,w3) = (18,15,10)。可能的可行解如下：(x1,x2,x3) (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.5Date2. 贪心策略求解度量标准的选择：三种不同的选择1）以 目标函数 作为度量标准即，每装入一件物品，就使背包背包获得 最大 可能的效益增量。该度量标准下的 处理规则： 按效益值的非增次序将物品一件件地放入到背包； 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量
8、标准，则在 剩下 的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。如：若 M=2,背包外还剩两件物品 i,j， 且有 (pi 4， wi 4) 和 (pj 3， wj 2)， 则下一步应选择 j而非 i放入背包：pi/2 = 2 pj 3Date实例分析（例 5.1)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) p1 p2 p3 首先将 物品 1放入背包，此时 x1 1， 背包获得 p1 25的效益增量，同时背包容量减少 w1 18个单位，剩余空间 M=2。其次考虑 物品 2和 3。就 M=2而言有，只能选择物品 2或 3的 一部分 装入背包。物品 2： 若 x2 2/15， 则 p2 x2 16/5 3.1物品 3： 若 x3 2/10， 则 p3 x3 3为使背包的效益有最大的增量，应选择 物品 2的 2/15装包，即x2 2/15 最后，背包装满， M=0， 故 物品 3将不能装入背包， x3 0 。背包最终可以获得 效益值 x1 p1 x2 p2 x3 p3 28.2 (次优解 ,非问题的最优解 )Date
