(25/18,24/15,15/10=(1.389,16,1.5)。首先考虑单位价值大的物品装 包,即将物品2装包,此时获得效益值24,背包的剩余容量是5。然 后考虑装物品3,由于物品3的重量超出背包的剩余容量,只能装入 该物品5/15=1/2,至此背包已经装满,所得的总的效益值为 24+15/2=315。比前面的装法的效益值大。实践证明,选择能产生最 优解的贪心准则是设计贪心算法的核心问题。以下给出贪心算法流程 的伪代码。 贪心算法抽象化控制流程 Greedy(A,n)∥A[1n]代表那个输入 solution={};∥解向量初始化为空集 fori from l to n do xSelect(A); if Feasible(solution, x)then solution=Union(solution, x); endif endfor return( solution) end greedy 这里 Selecte(A)是按照谈心准则选取A种的输入项; Feasible( solution, x)是判断已知的解的部分 solution与新选取的x的结合 Union( solution, x)是否是可行解。过程〔redy描述了用贪心策略设计算法的主要工 作和基本控制流程。一旦给出一个特定的问题,就可将 Select, Feasible
(25/18, 24/15, 15/10)=(1.389, 1.6, 1.5)。首先考虑单位价值大的物品装 包，即将物品 2 装包，此时获得效益值 24，背包的剩余容量是 5。然 后考虑装物品 3，由于物品 3 的重量超出背包的剩余容量，只能装入 该物品 5/15=1/2, 至此背包已经装满，所得的总的效益值为 24+15/2=31.5。比前面的装法的效益值大。实践证明，选择能产生最 优解的贪心准则是设计贪心算法的核心问题。以下给出贪心算法流程 的伪代码。 贪心算法抽象化控制流程 Greedy(A, n) // A[1:n]代表那个输入 solution={}; //解向量初始化为空集 for i from 1 to n do x=Select(A); if Feasible(solution, x) then solution=Union(solution, x); endif endfor return(solution); end Greedy 这里 Select(A)是按照谈心准则选取 A 种的输入项； Feasible(solution, x)是判断已知的解的部分solution与新选取的x的结合Union(solution, x)是否是可行解。过程 Greedy 描述了用贪心策略设计算法的主要工 作和基本控制流程。一旦给出一个特定的问题，就可将 Select，Feasible
和 Union具体化并付诸实现。 §2作业排序问题 ●活动安排问题 我们首先从活动安排这一简单课题入手。该问题要求高效地安排 系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的 方法使得尽可能多的活动能够兼容地使用公共资源。 问题:已知n个活动E={1,2,…,n}要求使用同一资源,第k 个活动要求的开始和结束时间为s,f,其中s<f,k=1,2,…,n 活动k与活动j称为相容的如果s>f或者s>f。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集。 解决这个问题的基本思路是在安排时应该将结束时间早的活动 尽量往前安排,好给后面的活动安排留出更多的空间,从而达到安排 最多活动的目标。据此,贪心准则应当是:在未安排的活动中挑选结 束时间最早的活动安排。在贪心算法中,将各项活动的开始时间和结 束时间分别用两个数组s和f存储,并使得数组中元素的顺序按结束 时间非减排列:f1≤f,≤…≤fn 活动安排贪心算法伪代码 Greedy Action(s,f,n)∥lln]、红ln]分别代表n项活动的起始 时间和结束时间,并且满足f1≤2]…≤fn l; solution={1};∥解向量初始化为空集 for i from 2 to n do
和 Union 具体化并付诸实现。 §2 作业排序问题 z 活动安排问题 我们首先从活动安排这一简单课题入手。该问题要求高效地安排 一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的 方法使得尽可能多的活动能够兼容地使用公共资源。 问题：已知 n 个活动 E={1, 2, … ,n}要求使用同一资源，第 k 个活动要求的开始和结束时间为 sk, fk, 其中 sk< fk, k=1, 2, … , n . 活动 k 与活动 j 称为相容的如果 sk> fj或者 sj> fk。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集。 解决这个问题的基本思路是在安排时应该将结束时间早的活动 尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排 最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结 束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结 束时间分别用两个数组 s 和 f 存储，并使得数组中元素的顺序按结束 时间非减排列：f1≤ f2≤…≤ fn。 活动安排贪心算法伪代码 GreedyAction(s, f，n) // s[1:n]、f[1:n]分别代表 n 项活动的起始 //时间和结束时间, 并且满足 f[1]≤ f[2]≤…≤ f[n] j=1; solution={1}; //解向量初始化为空集 for i from 2 to n do
fs≥fthe solution= solution u};∥将j加入解中 endif endfor return(solution) end greedy 例子设待安排的11个活动的开始时间和结束时间按结束时间的 非减次序排列如下 k1234 67891011 s]13053568√|8212y 562891011121314 解集合为{1,4-8,11容易证明算法 Greedy Action所得到的解是最 优解。 带限期作业安排问题 将活动排序问题加上效益条件,即是下面的单机作业排序问题。 为使问题简化,我们假定完成每项作业的时间都是都是一样的,比如 都是1。 问题:已知n项作业E={1,2,…,n}要求使用同台机器完成, 而且每项作业需要的时间都是1。第k项作业要求在时间f之前完成 而且完成这项作业将获得效益pk,k=1,2,…,n。E的子集称为相 容的,如果它们可以被安排由一台机器完成(该台机器在同一时刻至
if si≥fj then solution=solution ∪ {j}; // 将 j 加入解中 j=i; endif endfor return(solution); end Greedy 例子 设待安排的 11 个活动的开始时间和结束时间按结束时间的 非减次序排列如下： k 1 2 3 4 5 6 7 8 9 10 11 s[k] 1√ 3 0 5√ 3 5 6 8√ 8 2 12√ f[k] 4 5 6 7 8 9 10 11 12 13 14 解集合为 {1,4,8,11}.容易证明算法 GreedyAction 所得到的解是最 优解。 z 带限期作业安排问题 将活动排序问题加上效益条件，即是下面的单机作业排序问题。 为使问题简化，我们假定完成每项作业的时间都是都是一样的，比如 都是 1。 问题： 已知 n 项作业 E={1, 2, … ,n}要求使用同台机器完成， 而且每项作业需要的时间都是 1。第 k 项作业要求在时间 fk之前完成, 而且完成这项作业将获得效益 pk，k=1, 2, … , n 。E 的子集称为相 容的，如果它们可以被安排由一台机器完成（该台机器在同一时刻至