准则选取A中的输入项；Feasiblesolutio
x是判断已知的解的部分solutio
与新选取的x的结合U
io
solutio
x是否是可行解。过程Greedy描述了用贪心策略设计算法的主要工作和基本控制流程。一旦给出一个特定的问题，就可将Select，Feasible和U
io
具体化并付诸实现。
§2作业排序问题
活动安排问题我们首先从活动安排这一简单问题入手。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能够兼容地使用公共资源。问题：已知
个活动E12…
，要求使用同一资源，第k个活动要求的开始和结束时间为skfk其中skfkk12…
活动k与活动j称为相容的如果skfj或者sjfk。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。解决这个问题的基本思路是在安排时应该将结束时间早结束时间早的活动尽量往前安结束时间早排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结束时间非减排列：f1≤f2≤…≤f
。程序521活动安排贪心算法伪代码GreedyActio
sf，
s1
、f1
分别代表
项活动的起始时间和结束时间并且满足f1≤f2≤…≤f
j1solutio
1解向量初始化forifrom2to
doifsi≥fjthe
solutio
solutio
∪j将j加入解中jie
dife
dforretur
solutio

f6
e
dGreedy例子设待安排的11个活动的开始时间和结束时间按结束时间的非减次序排列如下：k123530645√7538659761088√119812102131112√14sk1√fk4
解集合为14811容易证明算法GreedyActio
所得到的解是最优解。带限期作业安排问题将活动排序问题加上效益条件，即是下面的单机作业排序问题。为使问题简化，我们假定完成每项作业的时间都是一样的，比如都是1。问题：已知
项作业E12…
要求使用同台机器完成，而且每项作业需要的时间都是1。k项作业要求在时间fk之前完成而且完成这项作业第将获得效益pk，k12…
。E的子集称为相容的，如果它们可以被安排由一台机器完成（该台机器在同一时刻至多进行一个作业）。带限期作业排序问题就是要在所给的作业集合中选出总效益值最大的相容子集。这个问题可以看作是活动安排问题的推广，作业i的起始时间为si：0≤si≤fi1而活动安排问题中的效益值可以r