1
第 4章 贪心算法
2
第 4章 贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的 局部最优 选择。当然，
希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，
最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
3
第 4章 贪心算法本章主要知识点：
4.1 活动安排问题
4.2 贪心算法的基本要素
4.3 最优装载
4.4 哈夫曼编码
4.5 单源最短路径
4.6 最小生成树
4.7 多机调度问题
4.8 贪心算法的理论基础
4
4.1 活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
5
4.1 活动安排问题设有 n个活动的集合 E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i都有一个要求使用该资源的起始时间 si和一个结束时间 fi,且 si <fi 。如果选择了活动 i，则它在半开时间区间 [si,fi)内占用资源。
若区间 [si,fi)与区间 [sj,fj)不相交，则称活动 i与活动 j是相容的。也就是说，当 si≥fj 或 sj≥fi 时，活动 i与活动 j相容。
6
4.1 活动安排问题在下面所给出的解活动安排问题的贪心算法 greedySelector,
public static int greedySelector(int [] s,int [] f,boolean a[])
{
int n=s.length-1;
a[1]=true;
int j=1;
int count=1;
for (int i=2;i<=n;i++) {
if (s[i]>=f[j]) {
a[i]=true;
j=i;
count++;
}
else a[i]=false;
}
return count;
}
各活动的起始时间和结束时间存储于数组 s和 f
中且按结束时间的非减序排列
7
4.1 活动安排问题由于输入的活动以其完成时间的 非减序 排列，所以算法 greedySelector每次总是选择 具有最早完成时间 的相容活动加入集合 A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是 使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
算法 greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需 O(n)的时间安排 n个活动，使最多的活动能相容地使用公共资源。
如果所给出的活动未按非减序排列，可以用 O(nlogn)
的时间重排。
8
4.1 活动安排问题例,设待安排的 11个活动的开始时间和结束时间按结束时间的非减序排列如下：
i 1 2 3 4 5 6 7 8 9 10 11
S[i] 1 3 0 5 3 5 6 8 8 2 12
f[i] 4 5 6 7 8 9 10 11 12 13 14
9
4.1 活动安排问题算法 greedySelector 的计算过程 如左图所示。
图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合 A
的活动，而空白长条表示的活动是当前正在检查相容性的活动。
10
4.1 活动安排问题若被检查的活动 i的开始时间 Si小于最近选择的活动 j的结束时间 fi，则不选择活动 i，否则选择活动 i加入集合 A中。
贪心算法并不总能求得问题的 整体最优解 。但对于活动安排问题，贪心算法 greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合 A的规模最大。这个结论可以用数学归纳法证明。
11
4.2 贪心算法的基本要素本节着重讨论可以用贪心算法求解的问题的一般特征。
对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。
但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有 2个重要的性质,贪心选择性质 和 最优子结构性质 。
12
4.2 贪心算法的基本要素
1.贪心选择性质所谓 贪心选择性质 是指所求问题的 整体最优解 可以通过一系列 局部最优 的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以 自底向上 的方式解各子问题，
而贪心算法则通常以 自顶向下 的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
13
4.2 贪心算法的基本要素
2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有 最优子结构性质 。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
14
4.2 贪心算法的基本要素
3.贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是 2类算法的一个共同点。但是，对于具有 最优子结构 的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究 2个经典的 组合优化问题,并以此说明贪心算法与动态规划算法的主要差别。
15
4.2 贪心算法的基本要素
0-1背包问题：
给定 n种物品和一个背包。物品 i的重量是 Wi，
其价值为 Vi，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品 i只有 2种选择，即装入背包或不装入背包。不能将物品 i装入背包多次，也不能只装入部分的物品 i。
16
4.2 贪心算法的基本要素
背包问题：
与 0-1背包问题类似，所不同的是在选择物品 i装入背包时,可以选择物品 i的一部分,而不一定要全部装入背包,1≤i≤n 。
这 2类问题都具有 最优子结构 性质，极为相似，但背包问题可以用贪心算法求解，而 0-1背包问题却不能用贪心算法求解。
17
4.2 贪心算法的基本要素用贪心算法解背包问题的基本步骤：
首先计算每种物品单位重量的价值 Vi/Wi，然后，依贪心选择策略，将尽可能多的 单位重量价值最高 的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总重量未超过
C，则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去，直到背包装满为止。
具体算法可描述如下页：
18
4.2 贪心算法的基本要素
public static float knapsack(float c,float [] w,float [] v,float [] x)
{
int n=v.length;
Element [] d = new Element [n];
for (int i = 0; i < n; i++) d[i] = new Element(w[i],v[i],i);
MergeSort.mergeSort(d);
int i;
float opt=0;
for (i=0;i<n;i++) x[i]=0;
for (i=0;i<n;i++) {
if (d[i].w>c) break;
x[d[i].i]=1;
opt+=d[i].v;
c-=d[i].w;
}
if (i<n){
x[d[i].i]=c/d[i].w;
opt+=x[d[i].i]*d[i].v;
}
return opt;
}
算法 knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为
O（ nlogn）。当然，
为了证明算法的正确性，还必须证明背包问题具有贪心选择性质 。
19
4.2 贪心算法的基本要素对于 0-1背包问题,贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲臵的背包空间使每公斤背包空间的价值降低了。事实上，在考虑 0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用 动态规划算法 求解的另一重要特征。
实际上也是如此，动态规划算法的确可以有效地解 0-1
背包问题。
20
4.3 最优装载有一批集装箱要装上一艘载重量为 c的轮船。其中集装箱 i的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
1.算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。
21
4.3 最优装载
public static float loading(float c,float [] w,int [] x)
{
int n=w.length;
Element [] d = new Element [n];
for (int i = 0; i < n; i++)
d[i] = new Element(w[i],i);
MergeSort.mergeSort(d);
float opt=0;
for (int i = 0; i < n; i++) x[i] = 0;
for (int i = 0; i < n && d[i].w <= c; i++) {
x[d[i].i] = 1;
opt+=d[i].w;
c -= d[i].w;
}
return opt;
}
其中 Element类说明为参见本书 P115
22
4.3 最优装载
2.贪心选择性质可以证明最优装载问题具有贪心选择性质 。
3.最优子结构性质最优装载问题具有最优子结构性质。
由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法 loading的正确性。
算法 loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。
23
4.4 哈夫曼编码哈夫曼编码 是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在 20%～ 90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 0,1串表示各字符的最优表示方式。
给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。
1.前缀码对每一个字符规定一个 0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为 前缀码 。
24
4.4 哈夫曼编码编码的前缀性质可以使译码方法非常简单。
表示 最优前缀码 的二叉树总是一棵 完全二叉树,
即树中任一结点都有 2个儿子结点。
平均码长 定义为：
使平均码长达到最小的前缀码编码方案称为给定编码字符集 C的 最优前缀码 。
)()()( cdcfTB T
Cc
25
4.4 哈夫曼编码
2.构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为 哈夫曼编码 。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T。
算法以 |C|个叶结点开始，执行 |C|－ 1次的,合并,
运算后产生最终所要求的树 T。
26
4.4 哈夫曼编码在书上给出的算法 huffmanTree中，编码字符集中每一字符 c的频率是 f(c)。 以 f为键值的优先队列 Q用在贪心选择 时有效地确定算法当前要合并的 2棵具有最小频率的树。一旦 2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的 2棵树的频率之和，并将新树插入优先队列 Q。经过 n－ 1次的合并后，优先队列中只剩下一棵树，即所要求的树 T。
算法 huffmanTree用最小堆实现优先队列 Q。初始化优先队列需要 O(n)计算时间，由于最小堆的
removeMin和 put运算均需 O(logn)时间,n－ 1次的合并总共需要 O(nlogn)计算时间。因此，关于 n个字符的哈夫曼算法的 计算时间 为 O(nlogn) 。
27
4.4 哈夫曼编码
3.哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有 贪心选择性质 和 最优子结构性质 。
(1)贪心选择性质
(2)最优子结构性质
28
4.5 单源最短路径给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另外，还给定 V中的一个顶点，称为 源 。现在要计算从源到所有其他各顶点的 最短路长度 。这里路的长度是指路上各边权之和。这个问题通常称为 单源最短路径问题 。
1.算法基本思想
Dijkstra算法是解单源最短路径问题的贪心算法。
29
4.5 单源最短路径其 基本思想 是，设臵顶点集合 S并不断地作 贪心选择 来扩充这个集合。一个顶点属于集合 S当且仅当从源到该顶点的最短路径长度已知。
初始时,S中仅含有源。设 u是 G的某一个顶点，把从源到 u且中间只经过 S中顶点的路称为从源到 u的特殊路径，并用数组 dist记录当前每个顶点所对应的最短特殊路径长度。 Dijkstra算法每次从 V-S中取出具有最短特殊路长度的顶点 u，将 u添加到 S中，同时对数组
dist作必要的修改。一旦 S包含了所有 V中顶点,dist
就记录了从源到所有其他顶点之间的最短路径长度。
30
4.5 单源最短路径例如,对右图中的有向图，应用 Dijkstra
算法计算从源顶点 1到其他顶点间最短路径的过程列在下页的表中。
31
4.5 单源最短路径迭代 S u dist[2] dist[3] dist[4] dist[5]
初始 {1} - 10 maxint 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60
4 {1,2,4,3,5} 5 10 50 30 60
Dijkstra算法的迭代过程：
32
4.5 单源最短路径
2.算法的正确性和计算复杂性
(1)贪心选择性质
(2)最优子结构性质
(3)计算复杂性对于具有 n个顶点和 e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么 Dijkstra算法的主循环体需要 时间。这个循环需要执行 n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。
)(nO
)( 2nO
)( 2nO
33
4.6 最小生成树设 G =(V,E)是无向连通带权图，即一个 网络 。 E中每条边 (v,w)的权为 c[v][w]。如果 G的子图 G’是一棵包含 G的所有顶点的树，则称 G’为 G的生成树。生成树上各边权的总和称为该生成树的 耗费 。在 G的所有生成树中，耗费最小的生成树称为 G的 最小生成树 。
网络的最小生成树在实际中有广泛应用。 例如,
在设计通信网络时，用图的顶点表示城市，用边 (v,w)
的权 c[v][w]表示建立城市 v和城市 w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。
34
4.6 最小生成树
1.最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的 Prim算法和 Kruskal算法 都可以看作是应用贪心算法设计策略的例子。尽管这 2个算法做贪心选择的方式不同，它们都利用了下面的 最小生成树性质,
设 G=(V,E)是连通带权图,U是 V的真子集。如果
(u,v)?E，且 u?U,v?V-U，且在所有这样的边中，
(u,v)的权 c[u][v]最小，那么一定存在 G的一棵最小生成树，它以 (u,v)为其中一条边。这个性质有时也称为
MST性质 。
35
4.6 最小生成树
2.Prim算法设 G=(V,E)是连通带权图,V={1,2,…,n}。
构造 G的最小生成树的 Prim算法的 基本思想 是：首先臵 S={1}，然后，只要 S是 V的真子集，就作如下的 贪心选择,选取满足条件 i?S,j?V-S，且 c[i][j]最小的边，将顶点 j添加到 S中。这个过程一直进行到 S=V时为止。
在这个过程中选取到的所有边恰好构成 G的一棵 最小生成树 。
36
4.6 最小生成树利用最小生成树性质和数学归纳法容易证明，
上述算法中的 边集合 T始终包含 G的某棵最小生成树中的边 。因此，在算法结束时,T中的所有边构成 G的一棵最小生成树。
例如,对于右图中的带权图，按 Prim算法 选取边的过程如下页图所示。
37
4.6 最小生成树
38
4.6 最小生成树在上述 Prim算法中，还应当考虑 如何有效地找出满足条件 i?S,j?V-S，且权 c[i][j]最小的边 (i,j)。实现这个目的的较简单的办法是设臵 2个数组 closest和
lowcost。
在 Prim算法执行过程中，先找出 V-S中使 lowcost值最小的顶点 j，然后根据数组 closest选取边
(j,closest[j］ )，最后将 j添加到 S中，并对 closest和
lowcost作必要的修改。
用这个办法实现的 Prim算法所需的 计算时间 为 )( 2nO
39
4.6 最小生成树
3.Kruskal算法
Kruskal算法构造 G的最小生成树的 基本思想 是，
首先将 G的 n个顶点看成 n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接 2个不同的连通分支：当查看到第 k条边 (v,w)时，如果端点 v和
w分别是当前 2个不同的连通分支 T1和 T2中的顶点时，
就用边 (v,w)将 T1和 T2连接成一个连通分支，然后继续查看第 k+1条边；如果端点 v和 w在当前的同一个连通分支中，就直接再查看第 k+1条边。这个过程一直进行到只剩下一个连通分支时为止。
40
4.6 最小生成树例如,对前面的连通带权图，按 Kruskal算法顺序得到的最小生成树上的边如下图所示。
41
4.6 最小生成树关于 集合的一些基本运算 可用于实现 Kruskal算法。
按权的递增顺序查看等价于对 优先队列 执行
removeMin运算。可以用 堆 实现这个优先队列。
对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型 并查集 UnionFind所支持的基本运算。
当图的边数为 e时,Kruskal算法所需的 计算时间是 。当 时,Kruskal算法比 Prim算法差，但当 时,Kruskal算法却比 Prim算法好得多。
)log( eeO )( 2ne
)( 2noe?
42
4.7 多机调度问题多机调度问题 要求给出一种作业调度方案，使所给的 n个作业在尽可能短的时间内由 m台机器加工处理完成。
这个问题是 NP完全问题,到目前为止还没有有效的解法。对于这一类问题,用 贪心选择策略 有时可以设计出较好的近似算法。
约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
43
4.7 多机调度问题采用 最长处理时间作业优先 的贪心选择策略可以设计出解多机调度问题的较好的近似算法。
按此策略，当 时，只要将机器 i的 [0,ti]时间区间分配给作业 i即可，算法只需要 O(1)时间。
当 时，首先将 n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为 O(nlogn)。
mn?
mn?
44
4.7 多机调度问题例如,设 7个独立作业 {1,2,3,4,5,6,7}由 3台机器 M1,M2和 M3加工处理。各作业所需的处理时间分别为 {2,14,4,16,6,5,3}。按算法 greedy产生的作业调度如下图所示，所需的加工时间为 17。
45
4.8 贪心算法的理论基础借助于 拟阵 工具，可建立关于贪心算法的较一般的理论。这个理论对 确定何时使用贪心算法 可以得到问题的整体最优解十分有用。
1.拟阵拟阵 M定义为满足下面 3个条件的有序对 (S,I)：
(1)S是非空有限集。
(2)I是 S的一类具有遗传性质的独立子集族，即若 B?I，
则 B是 S的独立子集，且 B的任意子集也都是 S的独立子集。空集?必为 I的成员。
(3)I满足交换性质，即若 A?I,B?I且 |A|<|B|，则存在某一元素 x?B-A，使得 A∪{x}?I。
46
4.8 贪心算法的理论基础例如,设 S是一给定矩阵中行向量的集合,I是 S的线性独立子集族，则由线性空间理论容易证明 (S,I)是一拟阵。拟阵的另一个例子是无向图 G=(V,E)的图拟阵
。
给定拟阵 M=(S,I)，对于 I中的独立子集 A?I，若 S
有一元素 x?A，使得将 x加入 A后仍保持独立性，即
A∪{x}? I,则称 x为 A的 可扩展元素 。
当拟阵 M中的独立子集 A没有可扩展元素时，称 A为极大独立子集 。
),( GGG ISM?
47
4.8 贪心算法的理论基础下面的关于 极大独立子集 的性质是很有用的。
定理 4.1,拟阵 M中所有极大独立子集大小相同。
这个定理可以用反证法证明。
若对拟阵 M=(S,I)中的 S指定权函数 W，使得对于任意 x?S，有 W(x)>0，则称拟阵 M为 带权拟阵 。依此权函数,S的任一子集 A的权定义为 。
2.关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的 最大权独立子集问题 。
Ax xWAW )()(
48
4.8 贪心算法的理论基础给定带权拟阵 M=(S,I)，确定 S的独立子集 A?I使得
W(A)达到最大。这种使 W(A)最大的独立子集 A称为拟阵
M的 最优子集 。由于 S中任一元素 x的权 W(x)是正的，因此,最优子集也一定是极大独立子集 。
例如,在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集 A的算法可用于解最小生成树问题。
下面给出求 带权拟阵最优子集 的贪心算法。该算法以具有正权函数 W的带权拟阵 M=(S,I)作为输入，经计算后输出 M的最优子集 A。
GM
49
4.8 贪心算法的理论基础
Set greedy (M,W)
{A=?;
将 S中元素依权值 W（大者优先）组成优先队列；
while (S!=?) {
S.removeMax(x);
if (A∪{x}?I) A=A∪{x};
}
return A
}
50
4.8 贪心算法的理论基础算法 greedy的计算时间复杂性为 。
引理 4.2(拟阵的贪心选择性质 )
设 M=(S,I)是具有权函数 W的带权拟阵，且 S中元素依权值从大到小排列。又设 x?S是 S中第一个使得 {x}
是独立子集的元素，则存在 S的最优子集 A使得 x?A。
算法 greedy在以贪心选择构造最优子集 A时，首次选入集合 A中的元素 x是单元素独立集中具有最大权的元素。此时可能已经舍弃了 S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。
))(l o g( nnfnnO?
51
4.8 贪心算法的理论基础引理 4.3,设 M=(S,I)是拟阵。若 S中元素 x不是空集的可扩展元素，则 x也不可能是 S中任一独立子集 A的可扩展元素。
引理 4.4(拟阵的最优子结构性质 )
设 x是求带权拟阵 M＝ (S,I)的最优子集的贪心算法 greedy所选择的 S中的第一个元素。那么，原问题可简化为求带权拟阵 M’=(S’,I’)的 最优子集 问题，其中：
S’={y|y?S且 {x,y}?I}
I’={B|B? S-{x}且 B∪{x}?I}
M’的权函数是 M的权函数在 S’上的限制 (称 M’为 M关于元素 x的 收缩 )。
52
4.8 贪心算法的理论基础定理 4.5(带权拟阵贪心算法的正确性 )
设 M＝ (S,I)是具有权函数 W的带权拟阵，算法
greedy返回 M的最优子集。
3.任务时间表问题给定一个 单位时间任务 的有限集 S。关于 S的一个时间表 用于描述 S中单位时间任务的执行次序。时间表中第 1个任务从时间 0开始执行直至时间 1结束，第 2个任务从时间 1开始执行至时间 2结束,…,第 n个任务从时间 n-1开始执行直至时间 n结束。
53
4.8 贪心算法的理论基础具有 截止时间 和 误时惩罚 的单位时间任务时间表问题可描述如下。
(1) n个单位时间任务的集合 S={1,2,…,n}；
(2) 任务 i的截止时间,1≤i≤n,1≤ ≤n,即要求任务 i在时间 之前结束；
(3) 任务 i的误时惩罚,1≤i≤n,即任务 i未在时间 之前结束将招致的 惩罚；若按时完成则无惩罚。
任务时间表问题 要求确定 S的一个时间表（最优时间表）使得总误时惩罚达到最小。
id id
id
iw
iwid
54
4.8 贪心算法的理论基础这个问题看上去很复杂，然而借助于 拟阵,可以用 带权拟阵的贪心算法 有效求解。
对于一个给定的 S的时间表，在截止时间之前完成的任务称为 及时任务,在截止时间之后完成的任务称为 误时任务 。
S的任一时间表可以调整成 及时优先形式,即其中所有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质。
类似地，还可将 S的任一时间表调整成为 规范形式,
其中及时任务先于误时任务，且及时任务依其截止时间的非减序排列。
55
4.8 贪心算法的理论基础首先可将时间表调整为及时优先形式，然后再进一步调整及时任务的次序。
任务时间表问题 等价于 确定最优时间表中 及时任务子集 A的问题。一旦确定了及时任务子集 A，将 A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务，即 S-A中各任务，由此产生 S的一个规范的最优时间表。
对时间 t=1,2,…,n,设 (A)是任务子集 A中所有截止时间是 t或更早的任务数。考察任务子集 A的独立性。
tN
56
4.8 贪心算法的理论基础引理 4.6,对于 S的任一任务子集 A，下面的各命题是等价的。
(1) 任务子集 A是独立子集。
(2) 对于 t=1,2,…,n,(A)≤t 。
(3) 若 A中任务依其截止时间非减序排列，则 A中所有任务都是及时的。
任务时间表问题 要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值之和达到最大。下面的 定理 表明可用带权拟阵的贪心算法解任务时间表问题。
tN
57
4.8 贪心算法的理论基础定理 4.7,设 S是带有截止时间的单位时间任务集,I
是 S的所有独立任务子集构成的集合。则有序对 (S,I)是拟阵。
由 定理 4.5可知，用带权拟阵的贪心算法可以求得最大权 (惩罚 )独立任务子集 A，以 A作为最优时间表中的及时任务子集，容易构造最优时间表。
任务时间表问题的贪心算法的 计算时间复杂性是 。其中 f(n)是用于检测任务子集 A的独立性所需的时间。用引理 4.6中性质 (2)容易设计一个时间算法来检测任务子集的独立性。因此，整个算法的计算时间 为 。具体算法 greedyJob可描述如 P130。)( 2nO
)(nO
))(l o g( nnfnnO?
58
4.8 贪心算法的理论基础用抽象数据类型并查集 UnionFind可对上述算法作进一步改进。如果不计预处理的时间，改进后的算法
fasterJob所需的 计算时间 为 。)lo g( * nnO
第 4章 贪心算法
2
第 4章 贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的 局部最优 选择。当然，
希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，
最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
3
第 4章 贪心算法本章主要知识点：
4.1 活动安排问题
4.2 贪心算法的基本要素
4.3 最优装载
4.4 哈夫曼编码
4.5 单源最短路径
4.6 最小生成树
4.7 多机调度问题
4.8 贪心算法的理论基础
4
4.1 活动安排问题活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
5
4.1 活动安排问题设有 n个活动的集合 E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i都有一个要求使用该资源的起始时间 si和一个结束时间 fi,且 si <fi 。如果选择了活动 i，则它在半开时间区间 [si,fi)内占用资源。
若区间 [si,fi)与区间 [sj,fj)不相交，则称活动 i与活动 j是相容的。也就是说，当 si≥fj 或 sj≥fi 时，活动 i与活动 j相容。
6
4.1 活动安排问题在下面所给出的解活动安排问题的贪心算法 greedySelector,
public static int greedySelector(int [] s,int [] f,boolean a[])
{
int n=s.length-1;
a[1]=true;
int j=1;
int count=1;
for (int i=2;i<=n;i++) {
if (s[i]>=f[j]) {
a[i]=true;
j=i;
count++;
}
else a[i]=false;
}
return count;
}
各活动的起始时间和结束时间存储于数组 s和 f
中且按结束时间的非减序排列
7
4.1 活动安排问题由于输入的活动以其完成时间的 非减序 排列，所以算法 greedySelector每次总是选择 具有最早完成时间 的相容活动加入集合 A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是 使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。
算法 greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需 O(n)的时间安排 n个活动，使最多的活动能相容地使用公共资源。
如果所给出的活动未按非减序排列，可以用 O(nlogn)
的时间重排。
8
4.1 活动安排问题例,设待安排的 11个活动的开始时间和结束时间按结束时间的非减序排列如下：
i 1 2 3 4 5 6 7 8 9 10 11
S[i] 1 3 0 5 3 5 6 8 8 2 12
f[i] 4 5 6 7 8 9 10 11 12 13 14
9
4.1 活动安排问题算法 greedySelector 的计算过程 如左图所示。
图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合 A
的活动，而空白长条表示的活动是当前正在检查相容性的活动。
10
4.1 活动安排问题若被检查的活动 i的开始时间 Si小于最近选择的活动 j的结束时间 fi，则不选择活动 i，否则选择活动 i加入集合 A中。
贪心算法并不总能求得问题的 整体最优解 。但对于活动安排问题，贪心算法 greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合 A的规模最大。这个结论可以用数学归纳法证明。
11
4.2 贪心算法的基本要素本节着重讨论可以用贪心算法求解的问题的一般特征。
对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。
但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有 2个重要的性质,贪心选择性质 和 最优子结构性质 。
12
4.2 贪心算法的基本要素
1.贪心选择性质所谓 贪心选择性质 是指所求问题的 整体最优解 可以通过一系列 局部最优 的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以 自底向上 的方式解各子问题，
而贪心算法则通常以 自顶向下 的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
13
4.2 贪心算法的基本要素
2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有 最优子结构性质 。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
14
4.2 贪心算法的基本要素
3.贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是 2类算法的一个共同点。但是，对于具有 最优子结构 的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究 2个经典的 组合优化问题,并以此说明贪心算法与动态规划算法的主要差别。
15
4.2 贪心算法的基本要素
0-1背包问题：
给定 n种物品和一个背包。物品 i的重量是 Wi，
其价值为 Vi，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品 i只有 2种选择，即装入背包或不装入背包。不能将物品 i装入背包多次，也不能只装入部分的物品 i。
16
4.2 贪心算法的基本要素
背包问题：
与 0-1背包问题类似，所不同的是在选择物品 i装入背包时,可以选择物品 i的一部分,而不一定要全部装入背包,1≤i≤n 。
这 2类问题都具有 最优子结构 性质，极为相似，但背包问题可以用贪心算法求解，而 0-1背包问题却不能用贪心算法求解。
17
4.2 贪心算法的基本要素用贪心算法解背包问题的基本步骤：
首先计算每种物品单位重量的价值 Vi/Wi，然后，依贪心选择策略，将尽可能多的 单位重量价值最高 的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总重量未超过
C，则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去，直到背包装满为止。
具体算法可描述如下页：
18
4.2 贪心算法的基本要素
public static float knapsack(float c,float [] w,float [] v,float [] x)
{
int n=v.length;
Element [] d = new Element [n];
for (int i = 0; i < n; i++) d[i] = new Element(w[i],v[i],i);
MergeSort.mergeSort(d);
int i;
float opt=0;
for (i=0;i<n;i++) x[i]=0;
for (i=0;i<n;i++) {
if (d[i].w>c) break;
x[d[i].i]=1;
opt+=d[i].v;
c-=d[i].w;
}
if (i<n){
x[d[i].i]=c/d[i].w;
opt+=x[d[i].i]*d[i].v;
}
return opt;
}
算法 knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为
O（ nlogn）。当然，
为了证明算法的正确性，还必须证明背包问题具有贪心选择性质 。
19
4.2 贪心算法的基本要素对于 0-1背包问题,贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲臵的背包空间使每公斤背包空间的价值降低了。事实上，在考虑 0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用 动态规划算法 求解的另一重要特征。
实际上也是如此，动态规划算法的确可以有效地解 0-1
背包问题。
20
4.3 最优装载有一批集装箱要装上一艘载重量为 c的轮船。其中集装箱 i的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
1.算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。
21
4.3 最优装载
public static float loading(float c,float [] w,int [] x)
{
int n=w.length;
Element [] d = new Element [n];
for (int i = 0; i < n; i++)
d[i] = new Element(w[i],i);
MergeSort.mergeSort(d);
float opt=0;
for (int i = 0; i < n; i++) x[i] = 0;
for (int i = 0; i < n && d[i].w <= c; i++) {
x[d[i].i] = 1;
opt+=d[i].w;
c -= d[i].w;
}
return opt;
}
其中 Element类说明为参见本书 P115
22
4.3 最优装载
2.贪心选择性质可以证明最优装载问题具有贪心选择性质 。
3.最优子结构性质最优装载问题具有最优子结构性质。
由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法 loading的正确性。
算法 loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。
23
4.4 哈夫曼编码哈夫曼编码 是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在 20%～ 90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 0,1串表示各字符的最优表示方式。
给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。
1.前缀码对每一个字符规定一个 0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为 前缀码 。
24
4.4 哈夫曼编码编码的前缀性质可以使译码方法非常简单。
表示 最优前缀码 的二叉树总是一棵 完全二叉树,
即树中任一结点都有 2个儿子结点。
平均码长 定义为：
使平均码长达到最小的前缀码编码方案称为给定编码字符集 C的 最优前缀码 。
)()()( cdcfTB T
Cc
25
4.4 哈夫曼编码
2.构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为 哈夫曼编码 。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T。
算法以 |C|个叶结点开始，执行 |C|－ 1次的,合并,
运算后产生最终所要求的树 T。
26
4.4 哈夫曼编码在书上给出的算法 huffmanTree中，编码字符集中每一字符 c的频率是 f(c)。 以 f为键值的优先队列 Q用在贪心选择 时有效地确定算法当前要合并的 2棵具有最小频率的树。一旦 2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的 2棵树的频率之和，并将新树插入优先队列 Q。经过 n－ 1次的合并后，优先队列中只剩下一棵树，即所要求的树 T。
算法 huffmanTree用最小堆实现优先队列 Q。初始化优先队列需要 O(n)计算时间，由于最小堆的
removeMin和 put运算均需 O(logn)时间,n－ 1次的合并总共需要 O(nlogn)计算时间。因此，关于 n个字符的哈夫曼算法的 计算时间 为 O(nlogn) 。
27
4.4 哈夫曼编码
3.哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有 贪心选择性质 和 最优子结构性质 。
(1)贪心选择性质
(2)最优子结构性质
28
4.5 单源最短路径给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另外，还给定 V中的一个顶点，称为 源 。现在要计算从源到所有其他各顶点的 最短路长度 。这里路的长度是指路上各边权之和。这个问题通常称为 单源最短路径问题 。
1.算法基本思想
Dijkstra算法是解单源最短路径问题的贪心算法。
29
4.5 单源最短路径其 基本思想 是，设臵顶点集合 S并不断地作 贪心选择 来扩充这个集合。一个顶点属于集合 S当且仅当从源到该顶点的最短路径长度已知。
初始时,S中仅含有源。设 u是 G的某一个顶点，把从源到 u且中间只经过 S中顶点的路称为从源到 u的特殊路径，并用数组 dist记录当前每个顶点所对应的最短特殊路径长度。 Dijkstra算法每次从 V-S中取出具有最短特殊路长度的顶点 u，将 u添加到 S中，同时对数组
dist作必要的修改。一旦 S包含了所有 V中顶点,dist
就记录了从源到所有其他顶点之间的最短路径长度。
30
4.5 单源最短路径例如,对右图中的有向图，应用 Dijkstra
算法计算从源顶点 1到其他顶点间最短路径的过程列在下页的表中。
31
4.5 单源最短路径迭代 S u dist[2] dist[3] dist[4] dist[5]
初始 {1} - 10 maxint 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60
4 {1,2,4,3,5} 5 10 50 30 60
Dijkstra算法的迭代过程：
32
4.5 单源最短路径
2.算法的正确性和计算复杂性
(1)贪心选择性质
(2)最优子结构性质
(3)计算复杂性对于具有 n个顶点和 e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么 Dijkstra算法的主循环体需要 时间。这个循环需要执行 n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。
)(nO
)( 2nO
)( 2nO
33
4.6 最小生成树设 G =(V,E)是无向连通带权图，即一个 网络 。 E中每条边 (v,w)的权为 c[v][w]。如果 G的子图 G’是一棵包含 G的所有顶点的树，则称 G’为 G的生成树。生成树上各边权的总和称为该生成树的 耗费 。在 G的所有生成树中，耗费最小的生成树称为 G的 最小生成树 。
网络的最小生成树在实际中有广泛应用。 例如,
在设计通信网络时，用图的顶点表示城市，用边 (v,w)
的权 c[v][w]表示建立城市 v和城市 w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。
34
4.6 最小生成树
1.最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的 Prim算法和 Kruskal算法 都可以看作是应用贪心算法设计策略的例子。尽管这 2个算法做贪心选择的方式不同，它们都利用了下面的 最小生成树性质,
设 G=(V,E)是连通带权图,U是 V的真子集。如果
(u,v)?E，且 u?U,v?V-U，且在所有这样的边中，
(u,v)的权 c[u][v]最小，那么一定存在 G的一棵最小生成树，它以 (u,v)为其中一条边。这个性质有时也称为
MST性质 。
35
4.6 最小生成树
2.Prim算法设 G=(V,E)是连通带权图,V={1,2,…,n}。
构造 G的最小生成树的 Prim算法的 基本思想 是：首先臵 S={1}，然后，只要 S是 V的真子集，就作如下的 贪心选择,选取满足条件 i?S,j?V-S，且 c[i][j]最小的边，将顶点 j添加到 S中。这个过程一直进行到 S=V时为止。
在这个过程中选取到的所有边恰好构成 G的一棵 最小生成树 。
36
4.6 最小生成树利用最小生成树性质和数学归纳法容易证明，
上述算法中的 边集合 T始终包含 G的某棵最小生成树中的边 。因此，在算法结束时,T中的所有边构成 G的一棵最小生成树。
例如,对于右图中的带权图，按 Prim算法 选取边的过程如下页图所示。
37
4.6 最小生成树
38
4.6 最小生成树在上述 Prim算法中，还应当考虑 如何有效地找出满足条件 i?S,j?V-S，且权 c[i][j]最小的边 (i,j)。实现这个目的的较简单的办法是设臵 2个数组 closest和
lowcost。
在 Prim算法执行过程中，先找出 V-S中使 lowcost值最小的顶点 j，然后根据数组 closest选取边
(j,closest[j］ )，最后将 j添加到 S中，并对 closest和
lowcost作必要的修改。
用这个办法实现的 Prim算法所需的 计算时间 为 )( 2nO
39
4.6 最小生成树
3.Kruskal算法
Kruskal算法构造 G的最小生成树的 基本思想 是，
首先将 G的 n个顶点看成 n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接 2个不同的连通分支：当查看到第 k条边 (v,w)时，如果端点 v和
w分别是当前 2个不同的连通分支 T1和 T2中的顶点时，
就用边 (v,w)将 T1和 T2连接成一个连通分支，然后继续查看第 k+1条边；如果端点 v和 w在当前的同一个连通分支中，就直接再查看第 k+1条边。这个过程一直进行到只剩下一个连通分支时为止。
40
4.6 最小生成树例如,对前面的连通带权图，按 Kruskal算法顺序得到的最小生成树上的边如下图所示。
41
4.6 最小生成树关于 集合的一些基本运算 可用于实现 Kruskal算法。
按权的递增顺序查看等价于对 优先队列 执行
removeMin运算。可以用 堆 实现这个优先队列。
对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型 并查集 UnionFind所支持的基本运算。
当图的边数为 e时,Kruskal算法所需的 计算时间是 。当 时,Kruskal算法比 Prim算法差，但当 时,Kruskal算法却比 Prim算法好得多。
)log( eeO )( 2ne
)( 2noe?
42
4.7 多机调度问题多机调度问题 要求给出一种作业调度方案，使所给的 n个作业在尽可能短的时间内由 m台机器加工处理完成。
这个问题是 NP完全问题,到目前为止还没有有效的解法。对于这一类问题,用 贪心选择策略 有时可以设计出较好的近似算法。
约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
43
4.7 多机调度问题采用 最长处理时间作业优先 的贪心选择策略可以设计出解多机调度问题的较好的近似算法。
按此策略，当 时，只要将机器 i的 [0,ti]时间区间分配给作业 i即可，算法只需要 O(1)时间。
当 时，首先将 n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为 O(nlogn)。
mn?
mn?
44
4.7 多机调度问题例如,设 7个独立作业 {1,2,3,4,5,6,7}由 3台机器 M1,M2和 M3加工处理。各作业所需的处理时间分别为 {2,14,4,16,6,5,3}。按算法 greedy产生的作业调度如下图所示，所需的加工时间为 17。
45
4.8 贪心算法的理论基础借助于 拟阵 工具，可建立关于贪心算法的较一般的理论。这个理论对 确定何时使用贪心算法 可以得到问题的整体最优解十分有用。
1.拟阵拟阵 M定义为满足下面 3个条件的有序对 (S,I)：
(1)S是非空有限集。
(2)I是 S的一类具有遗传性质的独立子集族，即若 B?I，
则 B是 S的独立子集，且 B的任意子集也都是 S的独立子集。空集?必为 I的成员。
(3)I满足交换性质，即若 A?I,B?I且 |A|<|B|，则存在某一元素 x?B-A，使得 A∪{x}?I。
46
4.8 贪心算法的理论基础例如,设 S是一给定矩阵中行向量的集合,I是 S的线性独立子集族，则由线性空间理论容易证明 (S,I)是一拟阵。拟阵的另一个例子是无向图 G=(V,E)的图拟阵
。
给定拟阵 M=(S,I)，对于 I中的独立子集 A?I，若 S
有一元素 x?A，使得将 x加入 A后仍保持独立性，即
A∪{x}? I,则称 x为 A的 可扩展元素 。
当拟阵 M中的独立子集 A没有可扩展元素时，称 A为极大独立子集 。
),( GGG ISM?
47
4.8 贪心算法的理论基础下面的关于 极大独立子集 的性质是很有用的。
定理 4.1,拟阵 M中所有极大独立子集大小相同。
这个定理可以用反证法证明。
若对拟阵 M=(S,I)中的 S指定权函数 W，使得对于任意 x?S，有 W(x)>0，则称拟阵 M为 带权拟阵 。依此权函数,S的任一子集 A的权定义为 。
2.关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟阵的 最大权独立子集问题 。
Ax xWAW )()(
48
4.8 贪心算法的理论基础给定带权拟阵 M=(S,I)，确定 S的独立子集 A?I使得
W(A)达到最大。这种使 W(A)最大的独立子集 A称为拟阵
M的 最优子集 。由于 S中任一元素 x的权 W(x)是正的，因此,最优子集也一定是极大独立子集 。
例如,在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集 A的算法可用于解最小生成树问题。
下面给出求 带权拟阵最优子集 的贪心算法。该算法以具有正权函数 W的带权拟阵 M=(S,I)作为输入，经计算后输出 M的最优子集 A。
GM
49
4.8 贪心算法的理论基础
Set greedy (M,W)
{A=?;
将 S中元素依权值 W（大者优先）组成优先队列；
while (S!=?) {
S.removeMax(x);
if (A∪{x}?I) A=A∪{x};
}
return A
}
50
4.8 贪心算法的理论基础算法 greedy的计算时间复杂性为 。
引理 4.2(拟阵的贪心选择性质 )
设 M=(S,I)是具有权函数 W的带权拟阵，且 S中元素依权值从大到小排列。又设 x?S是 S中第一个使得 {x}
是独立子集的元素，则存在 S的最优子集 A使得 x?A。
算法 greedy在以贪心选择构造最优子集 A时，首次选入集合 A中的元素 x是单元素独立集中具有最大权的元素。此时可能已经舍弃了 S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。
))(l o g( nnfnnO?
51
4.8 贪心算法的理论基础引理 4.3,设 M=(S,I)是拟阵。若 S中元素 x不是空集的可扩展元素，则 x也不可能是 S中任一独立子集 A的可扩展元素。
引理 4.4(拟阵的最优子结构性质 )
设 x是求带权拟阵 M＝ (S,I)的最优子集的贪心算法 greedy所选择的 S中的第一个元素。那么，原问题可简化为求带权拟阵 M’=(S’,I’)的 最优子集 问题，其中：
S’={y|y?S且 {x,y}?I}
I’={B|B? S-{x}且 B∪{x}?I}
M’的权函数是 M的权函数在 S’上的限制 (称 M’为 M关于元素 x的 收缩 )。
52
4.8 贪心算法的理论基础定理 4.5(带权拟阵贪心算法的正确性 )
设 M＝ (S,I)是具有权函数 W的带权拟阵，算法
greedy返回 M的最优子集。
3.任务时间表问题给定一个 单位时间任务 的有限集 S。关于 S的一个时间表 用于描述 S中单位时间任务的执行次序。时间表中第 1个任务从时间 0开始执行直至时间 1结束，第 2个任务从时间 1开始执行至时间 2结束,…,第 n个任务从时间 n-1开始执行直至时间 n结束。
53
4.8 贪心算法的理论基础具有 截止时间 和 误时惩罚 的单位时间任务时间表问题可描述如下。
(1) n个单位时间任务的集合 S={1,2,…,n}；
(2) 任务 i的截止时间,1≤i≤n,1≤ ≤n,即要求任务 i在时间 之前结束；
(3) 任务 i的误时惩罚,1≤i≤n,即任务 i未在时间 之前结束将招致的 惩罚；若按时完成则无惩罚。
任务时间表问题 要求确定 S的一个时间表（最优时间表）使得总误时惩罚达到最小。
id id
id
iw
iwid
54
4.8 贪心算法的理论基础这个问题看上去很复杂，然而借助于 拟阵,可以用 带权拟阵的贪心算法 有效求解。
对于一个给定的 S的时间表，在截止时间之前完成的任务称为 及时任务,在截止时间之后完成的任务称为 误时任务 。
S的任一时间表可以调整成 及时优先形式,即其中所有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质。
类似地，还可将 S的任一时间表调整成为 规范形式,
其中及时任务先于误时任务，且及时任务依其截止时间的非减序排列。
55
4.8 贪心算法的理论基础首先可将时间表调整为及时优先形式，然后再进一步调整及时任务的次序。
任务时间表问题 等价于 确定最优时间表中 及时任务子集 A的问题。一旦确定了及时任务子集 A，将 A中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任务，即 S-A中各任务，由此产生 S的一个规范的最优时间表。
对时间 t=1,2,…,n,设 (A)是任务子集 A中所有截止时间是 t或更早的任务数。考察任务子集 A的独立性。
tN
56
4.8 贪心算法的理论基础引理 4.6,对于 S的任一任务子集 A，下面的各命题是等价的。
(1) 任务子集 A是独立子集。
(2) 对于 t=1,2,…,n,(A)≤t 。
(3) 若 A中任务依其截止时间非减序排列，则 A中所有任务都是及时的。
任务时间表问题 要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值之和达到最大。下面的 定理 表明可用带权拟阵的贪心算法解任务时间表问题。
tN
57
4.8 贪心算法的理论基础定理 4.7,设 S是带有截止时间的单位时间任务集,I
是 S的所有独立任务子集构成的集合。则有序对 (S,I)是拟阵。
由 定理 4.5可知，用带权拟阵的贪心算法可以求得最大权 (惩罚 )独立任务子集 A，以 A作为最优时间表中的及时任务子集，容易构造最优时间表。
任务时间表问题的贪心算法的 计算时间复杂性是 。其中 f(n)是用于检测任务子集 A的独立性所需的时间。用引理 4.6中性质 (2)容易设计一个时间算法来检测任务子集的独立性。因此，整个算法的计算时间 为 。具体算法 greedyJob可描述如 P130。)( 2nO
)(nO
))(l o g( nnfnnO?
58
4.8 贪心算法的理论基础用抽象数据类型并查集 UnionFind可对上述算法作进一步改进。如果不计预处理的时间，改进后的算法
fasterJob所需的 计算时间 为 。)lo g( * nnO
