2.贪心方法的一般策略 问题的一般特征：问题的解是由个输入的、满足某些事先给定的条 件的子集组成。 1)一般方法 根据题意，.选取一种度量标准。然后按照这种度量标准对个输入排 序，并按序二次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起 不能产生二个可行解，则不把此输入加到这部分解屯。否对，将当前输 入 合并到部分解中从而得到包含当前输入的新的部分解。 2)贪心方法 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法 注：贪心解♀最优解 直接将目标函数作为量度标准也不一定能够得到问题的最 优解 3)使用贪心策略求解的关键 选取能够得到问题最优解的量度标准
2. 贪心方法的一般策略 问题的一般特征：问题的解是由n个输入的、满足某些事先给定的条 件的子集组成。 1）一般方法 根据题意，选取一种度量标准。然后按照这种度量标准对n个输入排 序，并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起 不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入 合并到部分解中从而得到包含当前输入的新的部分解。 2）贪心方法 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法 注： 贪心解 ＝ 最优解 3）使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。 直接将目标函数作为量度标准也不一定能够得到问题的最 优解 ？
3.贪心方法的抽象化控制描述 returnprocedure GREEDY(A,n) A(1:n)包含n个输入W solutions-Φ ∥将解向量solution初始化为空/ for i1 to n do X←一SELECT(A)/按照度量标准，从A中选择一个 输入，其值赋予X,并将之从A中删除W if FEASIBLE(solution,x)then /判定x是否可以包 含在解向量中，即是否能共同构成可行解Ⅱ solution←-UNION(solution,x)W将x和当前的解 向量合并成新的解向量，并修改目标函数川 endif repeat end GREEDY
3. 贪心方法的抽象化控制描述 returnprocedure GREEDY(A,n) //A(1:n)包含n个输入// solution←Φ //将解向量solution初始化为空// for i←1 to n do x←SELECT(A) //按照度量标准，从A中选择一个 输入，其值赋予x, 并将之从A中删除// if FEASIBLE(solution,x) then //判定x是否可以包 含在解向量中， 即是否能共同构成可行解// solution←UNION(solution,x) //将x和当前的解 向量合并成新的解向量，并修改目标函数// endif repeat end GREEDY
4.2背包问题 1.问题的描述 己知n种物品具有重量(W1,w2,,wn)和效益值(p1,P2,,Pn),及一 个可容纳M重量的背包；设当物品全部或一部分x放入背包将得到； x的效益，这里，0≤X1≤1，p1>0。 问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？ 分析：①装入背包的总重量不能超过M ② 如果所有物品的总重量不超过M,即∑w,x≤M,则把所有 的物品都装入背包中将获得最大可能的数益值。 ③如果物品的总重量超过了M,则将有物品不能（全部）装 入背包中。由于0≤xi≤1，所以可以把物品的一部分装入背包， 所以最终背包中可刚好装入重量为M的若干物品（整个或一部分） 目标：使装入背包的物品的总效益达到最大
4.2 背包问题 1.问题的描述 已知n种物品具有重量(w1 ,w2 ,…,wn)和效益值(p1 ,p2 ,…,pn) ，及一 个可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pi xi的效益，这里，0≤ xi ≤1, pi >0。 问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？ in i i w x 1 ② 如果所有物品的总重量不超过M，即 ≤M，则把所有 的物品都装入背包中将获得最大可能的效益值。 ③ 如果物品的总重量超过了M，则将有物品不能（全部）装 入背包中。由于0≤xi≤1，所以可以把物品的一部分装入背包， 所以最终背包中可刚好装入重量为M的若干物品（整个或一部分） 目标：使装入背包的物品的总效益达到最大。 分析：① 装入背包的总重量不能超过M
问题的形式描述 目标函数： ∑p,x l≤i≤n 约束条件： ∑w,x≤M 1≤i≤n 0≤x,≤1，p>0,w>0,1≤i≤n 可行解：满足上述约束条件的任一集合(X1,X2,,X)都是问 题的一个可行解一可行解可能有多个。 (仪1，x2,×n)称为问题的一个解向量 最优解：能够使目标函数取最大值的可行解是问题的最优解 一最优解也可能有多个
问题的形式描述 in i i p x 1 x p w i n w x M i i i i n i i 0 1, 0, 0,1 1 可 行 解： 满足上述约束条件的任一集合(x1 ,x2 ,…,xn ) 都是问 题的一个可行解——可行解可能有多个。 (x1 ,x2 ,…,xn )称为问题的一个解向量 最 优 解：能够使目标函数取最大值的可行解是问题的最优解。 ——最优解也可能有多个。 约束条件： 目标函数：
例5.1背包问题的实例 设，n=3,M=20, (p1,P2,P3)=(25,24,15),(W1,W2,W3)=（18,15,10)。 可能的可行解如下： (X1X2X3) ∑w,x ∑p,x ① (112,113,1/4) 16.5 24.25 /没有放满背包川 ② (1,2/15,0) 20 28.2 ③ (0,23, 1) 20 31 ④(0,1, 112) 20 31.5
例5.1 背包问题的实例 设，n=3，M=20， (p1 ,p2 ,p3 ) = (25,24,15)， (w1 ,w2 ,w3 ) = (18,15,10)。 可能的可行解如下： i i p x i i w x ① (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 (x1 ,x2 ,x3 )