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 的子集称为相 容的，如果它们可以被安排由一台机器完成（该台机器在同一时刻至