- 7.1 贪心法概述
- 7.1.1 什么是贪心法
- 7.1.2 用贪心法求解的问题应具有的性质
- 1. 贪心选择性质
- 2. 最优子结构性质
- 7.1.3 贪心法的一般求解过程
- 7.2 求解活动安排问题
- 7.3 求解背包问题
- 7.4 求解田忌赛马问题
- 7.5 哈夫曼编码
- 7.6 求解流水作业调度问题
- 7.7 求解最优装载问题
- 7.8 求解多机调度问题
- 其他题目
贪心法 Greedy Algorithm 是一种典型的算法设计策略，用于求解问题的最优解，这里介绍用贪心法求解问题的一般方法（尤其是贪心证明），并讨论一些采用贪心法求解的经典示例。
7.1 贪心法概述 7.1.1 什么是贪心法
贪心法的基本思路是，在对问题求解时、总是做出在当前看来是最好的选择，这个局部最优选择仅依赖以前的决策，不依赖于以后的决策——也就是说贪心法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。
人们通常希望找到全局最优解，那么贪心法是不是没有价值呢？答案是否定的，这是因为在某些求解问题中，当满足一定的条件时，这些局部最优解就转变成了全局最优解，所以贪心法的困难部分，就是要证明所设计的算法确实是整体最优解、或求解了它要解决的问题。
在求解问题时，这些问题通常直接给出、或者可以分析出某些「约束条件」，满足约束条件的问题解称为可行解。
另外，从要求解的问题直接给出、或者可以分析出「衡量可行解好坏的目标函数」，使目标函数取最大（或最小）值的可行解，称为最优解。
例如，求解一个带权无向图 G G G 中从顶点 i i i 到顶点 j ( i ≠ j ) j\ (i \ne j) j (i=j) 的最短路径，可以分析出：这样的最短路径一定是简单路径，所以：
- 约束条件：求解的路径为
{
(
i
,
i
1
)
,
(
i
1
,
i
2
)
,
…
,
(
i
m
,
j
)
}
\{ (i, i_1),\ (i_1, i_2),\ \dots,\ (i_{m}, j) \}
{(i,i1), (i1,i2), …, (im,j)} ，其中
(
i
,
i
1
)
,
(
i
1
,
i
2
)
,
…
,
(
i
m
,
j
)
(i, i_1),\ (i_1, i_2),\ \dots,\ (i_m, j)
(i,i1), (i1,i2), …, (im,j) 均为图
G
G
G 的边，且
i
k
(
1
≤
k
≤
m
)
i_k\ (1 \le k \le m)
ik (1≤k≤m) 均不相同。
- 目标函数就是要使这样的路径最短，即
min
p
a
t
h
l
e
n
g
t
h
{
(
i
,
i
1
)
,
(
i
1
,
i
2
)
,
…
,
(
i
m
,
j
)
}
\min_{pathlength} \{(i, i_1),\ (i_1, i_2),\ \dots,\ (i_{m}, j) \}
minpathlength{(i,i1), (i1,i2), …, (im,j)} ，其中
p
a
t
h
l
e
n
g
t
h
=
w
(
i
,
i
1
)
+
w
(
i
1
,
i
2
)
+
⋯
+
w
(
i
m
,
j
)
pathlength = w(i, i_1) + w(i_1, i_2) + \dots + w(i_m, j)
pathlength=w(i,i1)+w(i1,i2)+⋯+w(im,j) ，
w
(
i
,
k
)
w(i, k)
w(i,k) 表示边
(
i
,
k
)
(i, k)
(i,k) 的权值。
贪心法从问题的某一个初始空解出发，采取「逐步构造最优解」的方法、向给定的目标前进，每一步决策产生
n
n
n 元组解
(
x
0
,
x
1
,
…
,
x
n
−
1
)
(x_0, x_1, \dots , x_{n-1})
(x0,x1,…,xn−1) 的一个分量。
每一步用作决策依据的选择准则，被称为最优度量标准或贪心准则，也就是说（？），在选择解向量的过程中，添加新的解分量
x
k
x_k
xk 后、形成的部分解
(
x
0
,
x
1
,
…
,
x
k
)
(x_0, x_1, \dots, x_k)
(x0,x1,…,xk) 不违反可行解约束条件。
每一次贪心选择都将所求问题简化为规模更小的子问题，并期望通过「每次所做的局部最优选择」产生出一个全局最优解。
例如前面的求最短路径问题，初始解为空，然后一步一步地添加最短路径的边，直到产生最短路径
(
i
,
i
1
)
,
(
i
1
,
i
2
)
,
…
,
(
i
m
,
j
)
}
(i, i_1),\ (i_1, i_2),\ \dots,\ (i_{m}, j) \}
(i,i1), (i1,i2), …, (im,j)} 。
计算机科学中的很多算法都属于贪心法。
例如，在 *** 作系统的磁盘管理中，有一个磁盘移臂调度问题，进程在执行时多次访问磁盘，按访问的先后次序构成一个I/O序列，I/O *** 作的数据存放在磁盘的各个柱面上，磁盘臂通过在这些柱面之间移动磁头、找到相关数据。
移动磁盘臂是要花费时间的，磁盘移臂调度的目的是使平均访问时间最小。
例如，某个磁盘访问序列为
98
,
183
,
37
,
122
,
14
,
124
,
65
,
67
98, 183, 37, 122, 14, 124, 65, 67
98,183,37,122,14,124,65,67 ，开始时磁头位于
53
53
53 柱面上。
磁盘移臂调度有多种算法，这里以先来先服务和最短寻道时间优先算法为例、进行讲解。
-
先来先服务算法是按I/O请求的先后次序执行，而不考虑它们要访问的物理位置。
它的执行过程，是将磁头从 53 53 53 移到 98 98 98 ，接着再移到 183 , 37 , 122 , 14 , 124 , 65 183, 37, 122, 14, 124, 65 183,37,122,14,124,65 ，最后移到 67 67 67 ，其过程如图7.1所示。
总的磁头移动为 640 = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 640 = 45 +85+146+85+108+110+59+2 640=45+85+146+85+108+110+59+2 。
-
最短寻道时间优先算法，让距离当前磁道最近的I/O请求先执行，即让移动磁头时间最短的那个I/O请求先执行、而不考虑I/O请求的先后次序。
这一算法的执行过程是：与开始磁头位置 53 53 53 最近的请求位于柱面 65 65 65 ，先执行位于柱面 65 65 65 的请求，将磁头移动到该位置，当位于柱面 65 65 65 时，下一个最近请求位于柱面 67 67 67 ，执行位于柱面 67 67 67 的请求，将磁头移动到该位置，如图7.2所示。
总的磁头移动为 236 = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 236 = 12 + 2 +30+23+84+24+2+59 236=12+2+30+23+84+24+2+59 个柱面，平均寻道长度为 236 / 8 = 29.5 236/8 = 29.5 236/8=29.5 。
不考虑其他因素，从中可以看到，最短寻道时间优先算法好于先来先服务算法。
实际上，最短寻道时间优先就是采用贪心法的思想。
这种思想在 *** 作系统算法设计中，多次体现出来。
在很多情况下，所有局部最优解合起来不一定构成整体最优解，所以贪心法不能保证对所有问题都得到整体最优解。
因此，采用贪心法求解最优解问题时必须证明，该算法的每一步上做出的选择、都必然最终导致问题的一个整体最优解。
对于许多问题，如背包问题、单源最短路径问题、最小生成树问题等，贪心法确实能产生整体最优解。
而在有些情况下，即使用贪心法不能得到整体最优解，其最终结果却与最优解很近似。
另外，贪心与递归（算法设计思想、而非实际编码过程）不同的是，推进的每一步不是依据某一固定的递归式，而是做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似子问题。
由于贪心法一般不会测试所有可能路径，而且容易过早做决定，因此有些问题可能不会找到最优解，能够采用贪心法求解的问题一般具有两个性质——贪心选择性质和最优子结构，所以贪心算法一般需要证明满足这两个性质。
这是指所求问题的整体最优解，可以通过一系列局部最优的选择（即贪心选择）来达到。
即，贪心法仅在当前状态下做出最好选择，即局部最优选择，然后再去求解做出这个选择后、产生的相应子问题的解。
它是贪心法可行的第一个基本要素，也是贪心算法和后面介绍的动态规划的主要区别。
对一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。
这通常采用数学归纳法证明：先考虑问题的一个整体最优解，并证明可以修改这个最优解，使其从贪心选择开始，在做出贪心选择后、原问题转化为规模较小的类似问题，这样通过每一步的贪心选择，最后可得到问题的整体最优解。
如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。
问题的最优子结构性质，是该问题可用动态规划算法、或贪心法求解的关键特征。
在证明问题是否具有最优子结构性质时，通常采用反证法来证明，先假设「由问题的最优解导出的子问题的解」不是最优的，然后证明在这个假设下，可以构造出比原问题的最优解更好的解，从而导致矛盾。
用贪心法求解问题的基本思路如下：
- 建立数学模型来描述问题。
- 把求解的问题分成若干个子问题。
- 对每个子问题求解，得到子问题的局部最优解。
- 把子问题的局部最优解，合并成原来解问题的一个解。
用贪心法求解问题的算法框架如下：
SolutionType Greedy(SType a[], int n) {
// 假设解向量(x0,x1,...,xn-1)类型为SolutionType,其分量为SType类型
SolutionType x = {}; // 初始时解向量不包含任何分量
for (int i = 0; i < n; ++i) { // 执行n步 *** 作
SType xi = Select(a); // 从输入a中选择一个当前最好的分量
if (Feasiable(xi)) // 判断xi是否包含在当前解中
solution = Union(x, xi); // 把xi分量合并形成x
}
return x; // 返回生成的最优解
}
7.2 求解活动安排问题
活动安排问题描述见5.8节，这里采用贪心法求解该问题。
注意，本问题的最优解是「选取兼容活动最多的个数」。
【问题求解】假设活动时间的参考原点为
0
0
0 。
一个活动
i
(
1
≤
i
≤
n
)
i\ (1 \le i\le n)
i (1≤i≤n) 用一个半闭区间
[
b
i
,
e
i
)
[b_i, e_i)
[bi,ei) 表示，当活动按结束时间（右端点）递增排序后，两个活动
[
b
i
,
e
i
)
[b_i, e_i)
[bi,ei) 和
[
b
j
,
e
j
)
[b_j, e_j)
[bj,ej) 兼容（满足
b
i
≥
e
j
b_i \ge e_j
bi≥ej 或
b
j
≥
e
i
b_j \ge e_i
bj≥ei ）实际上就是指它们不相交。
用数组
A
A
A 存放所有的活动，
A
[
i
]
.
b
(
1
≤
i
≤
n
)
A[i].b\ (1\le i \le n)
A[i].b (1≤i≤n) 存放活动起始时间，
A
[
i
]
.
e
A[i].e
A[i].e 存放活动结束时间。
采用贪心法的策略是：每一步总是选择这样一个活动来占用资源，它能够使得余下的未调度的时间最大化，使得兼容的活动尽可能多。
为此，先按活动结束时间递增排序，再从头开始、依次选择兼容活动（用
B
B
B 集合表示），从而得到最大兼容活动子集（包含兼容活动个数最多的子集）。
由于活动按结束时间递增排序，每次总是选择最早完成的兼容活动加入集合
B
B
B 中，所以选择的兼容活动为未安排的活动留下尽可能多的时间，也就是使得剩余的可安排时间段极大化，以便安排尽可能多的兼容活动。
例如，对于表7.1所示的
n
=
11
n = 11
n=11 个活动（已按结束时间递增排序）
A
=
{
[
1
,
4
)
,
[
3
,
5
)
,
[
0
,
6
)
,
[
5
,
7
)
,
[
3
,
8
)
,
[
5
,
9
)
,
[
6
,
10
)
,
[
8
,
11
)
,
[
8
,
12
)
,
[
2
,
13
)
,
[
12
,
15
)
}
A = \{ [1, 4),\ [3, 5),\ [0, 6),\ [5, 7),\ [3, 8),\ [5, 9),\ [6, 10),\ [8, 11),\ [8, 12),\ [2, 13),\ [12, 15)\}
A={[1,4), [3,5), [0,6), [5,7), [3,8), [5,9), [6,10), [8,11), [8,12), [2,13), [12,15)} 。
设前一个兼容活动的结束时间为 p r e E n d preEnd preEnd（初始时为参考原点 0 0 0 ），求最大兼容活动子集 B B B 的过程如下：
-
i
=
1
i = 1
i=1 ：
p
r
e
E
n
d
=
0
preEnd = 0
preEnd=0 ，活动
1
[
1
,
4
)
1\ [1, 4)
1 [1,4) 的开始时间大于
0
0
0 ，选择它、
p
r
e
E
n
d
=
preEnd =
preEnd= 活动
1
1
1 的结束时间
=
4
= 4
=4 ，
B
=
{
[
1
,
4
)
}
B = \{[1, 4)\}
B={[1,4)} 。
-
i
=
2
i = 2
i=2 ：活动
2
[
3
,
5
)
2\ [3, 5)
2 [3,5) 的开始时间小于
p
r
e
E
n
d
preEnd
preEnd ，不选取。
-
i
=
3
i = 3
i=3 ：活动
3
[
0
,
6
)
3\ [0, 6)
3 [0,6) 的开始时间小于
p
r
e
E
n
d
preEnd
preEnd ，不选取。
-
i
=
4
i = 4
i=4 ：活动
4
[
5
,
7
)
4\ [5, 7)
4 [5,7) 的开始时间大于
p
r
e
E
n
d
preEnd
preEnd ，选择它、
p
r
e
E
n
d
=
7
preEnd = 7
preEnd=7 ，
B
=
{
[
1
,
4
)
,
[
5
,
7
)
}
B = \{ [1, 4),\ [5, 7)\}
B={[1,4), [5,7)} 。
-
i
=
5
i = 5
i=5 ：活动
5
[
3
,
8
)
5\ [3, 8)
5 [3,8) 的开始时间小于
p
r
e
E
n
d
preEnd
preEnd ，不选取。
-
i
=
6
i = 6
i=6 ：活动
6
[
5
,
9
)
6\ [5, 9)
6 [5,9) 的开始时间小于
p
r
e
E
n
d
preEnd
preEnd ，不选取。
-
i
=
7
i = 7
i=7 ：活动
7
[
6
,
10
)
7\ [6, 10)
7 [6,10) 的开始时间小于
p
r
e
E
n
d
preEnd
preEnd ，不选取。
-
i
=
8
i = 8
i=8 ：活动
8
[
8
,
11
)
8\ [8, 11)
8 [8,11) 的开始时间大于
p
r
e
E
n
d
preEnd
preEnd ，选择它、
p
r
e
E
n
d
=
11
preEnd = 11
preEnd=11 ，
B
=
{
[
1
,
4
)
,
[
5
,
7
)
,
[
8
,
11
)
}
B = \{ [1, 4),\ [5, 7),\ [8, 11)\}
B={[1,4), [5,7), [8,11)} 。
-
i
=
9
i = 9
i=9 ：活动
9
[
8
,
12
)
9\ [8, 12)
9 [8,12) 的开始时间小于
p
r
e
E
n
d
preEnd
preEnd ，不选取。
-
i
=
10
i = 10
i=10 ：活动
10
[
2
,
13
)
10\ [2, 13)
10 [2,13) 的开始时间小于
p
r
e
E
n
d
preEnd
preEnd ，不选取。
-
i
=
11
i = 11
i=11 ：活动
11
[
12
,
15
)
11\ [12, 15)
11 [12,15) 的开始时间大于
p
r
e
E
n
d
preEnd
preEnd ，选择它、
p
r
e
E
n
d
=
15
preEnd = 15
preEnd=15 ，
B
=
{
[
1
,
4
)
,
[
5
,
7
)
,
[
8
,
11
)
,
[
12
,
15
)
}
B= \{ [1, 4),\ [5, 7),\ [8, 11),\ [12, 15)\}
B={[1,4), [5,7), [8,11), [12,15)} 。
所以最后选择的最大兼容活动子集为 B = { 1 , 4 , 8 , 11 } B = \{1, 4, 8, 11\} B={1,4,8,11} 。
完整程序如下所示：
#include 上述程序的运行结果如下：
【算法分析】算法的时间主要花费在排序上，排序时间为
O
(
n
log
2
n
)
O(n\log_2 n)
O(nlog2n) ，所以整个算法的时间复杂度为
O
(
n
log
2
n
)
O(n\log_2 n)
O(nlog2n) 。
【算法证明】通常，证明一个贪心选择得出的解是最优解的一般方法是，构造一个初始最优解，然后对该解进行修正，使其第一步为一个贪心选择，证明总是存在一个以贪心选择开始的求解方案。
对于本问题，所有活动按结束时间递增排序后，就要证明：若
X
X
X 是活动安排问题
A
A
A 的最优解，
X
=
X
′
∪
{
1
}
X = X^{'} \cup \{ 1\}
X=X′∪{1} ，则
X
′
X^{'}
X′ 是
A
′
=
{
i
∈
A
∣
b
i
≥
e
1
}
A^{'} = \{ i \in A \mid b_i \ge e_1 \}
A′={i∈A∣bi≥e1} 的活动安排问题的最优解。
- 首先证明总存在一个以活动
1
1
1 开始的最优解。
假设第一个选中的活动为 k ( k ≠ 1 ) k\ (k \ne 1) k (k=1) ，可以构造另一个最优解 Y Y Y ， Y Y Y 中的活动是兼容的， Y Y Y 与 X X X 的活动数相同。
那么用活动 1 1 1 取代活动 k k k 得到 Y ′ Y' Y′ ，因为 e 1 ≤ e k e_1 \le e_k e1≤ek ，所以 Y ′ Y' Y′ 中的活动是兼容的，即 Y ′ Y' Y′ 也是最优的，这就说明总存在一个以活动 1 1 1 开始的最优解。
- 当做出了对活动
1
1
1 的贪心选择后，原问题就变成了「在活动
2
2
2 、……、活动
n
n
n 中找与活动
1
1
1 兼容的那些活动」的子问题，可见在每次贪心选择后，留下的是「一个与原问题具有相同形式的最优化子问题」。
此时要证明，如果 X X X 为原问题的一个最优解，则 X ′ = X − { 1 } X' = X - \{ 1\} X′=X−{1} 也是活动选择问题 A ′ = { i ∈ A ∣ b i ≥ e 1 } A' = \{ i \in A \mid b_i \ge e_1 \} A′={i∈A∣bi≥e1} 的一个最优解。
采用反证法，如果能找到一个 A ′ A' A′ 的、含有比 X ′ X' X′ 更多活动的解 Y ′ Y' Y′ ，则将活动 1 1 1 加入 Y ′ Y' Y′ 后，就得到 A A A 的一个包含比 X X X 更多活动的解 Y Y Y ，这就与 X X X 是最优解的假设矛盾。所以不存在一个 A ′ A' A′ 的、含有比 X ′ X' X′ 更多活动的解 Y ′ Y' Y′ ，即 X ′ X' X′ 是 A ′ A' A′ 的最优解。
从而，问题 A A A 的最优解 X X X 包含其子问题 A ′ A' A′ 的最优解 X ′ X' X′ ，最优子结构性质得证。
【例7.1】求解畜栏保留问题。
农村有
n
n
n 头牛，每头牛有一个特定的时间区间
[
b
,
e
]
[b, e]
[b,e] 在畜栏里挤牛奶，并且一个畜栏里在任何时刻只能有一头牛挤奶。
现在，农场主希望知道最少畜栏能够满足上述要求，并给出每头牛被安排的方案。
对于多种可行方案，输出一种即可。
解：牛的编号为
1
∼
n
1 \sim n
1∼n ，每头牛的挤奶时间相当于一个活动，与前面的活动安排问题不同，这里的活动时间是闭区间，例如
[
2
,
4
]
,
[
4
,
7
]
[2, 4], [4, 7]
[2,4],[4,7] 是交叉的，它们不是兼容活动。
采取与求解活动安排问题类似的贪心思路，将所有活动这样排序：结束时间相同就按开始时间递增排序，否则按结束时间递增排序。
求出一个最大兼容活动子集，将他们安排在一个畜栏中（畜栏编号为
1
1
1 ）；如果没有安排完，在剩余的活动中求下一个最大兼容活动子集，将它们安排在另一个畜栏中（畜栏编号为
2
2
2 ），依次类推。
也就是说，最大兼容活动子集的个数就是最少畜栏个数。
如图7.3所示，由一个活动集合产生三个最大兼容活动子集：
其过程是：用数组
A
A
A 存放所有活动，先将活动集合按上述方法排序，图中的活动集合是排序后的结果。
同时，建立一个活动标记数组
a
n
s
ans
ans ，
a
n
s
[
i
]
ans[i]
ans[i] 表示编号为
A
[
i
]
.
n
o
A[i].no
A[i].no 的牛安排挤奶的畜栏编号（从
1
1
1 开始），
a
n
s
[
i
]
=
0
ans[i]=0
ans[i]=0 表示该牛尚未安排畜栏，将所有元素设置为
0
0
0 ，置当前选取的畜栏编号
n
u
m
=
1
num = 1
num=1 ；从第一个活动开始寻找最大兼容活动子集
1
1
1 ，将其中所有活动编号
i
i
i 对应的
a
n
s
[
i
]
ans[i]
ans[i] 设置为
n
u
m
(
1
)
num(1)
num(1) ；
n
u
m
=
2
num = 2
num=2 ，在所有
a
n
s
[
i
]
=
0
ans[i] = 0
ans[i]=0 的活动集合中，寻找最大兼容活动子集
2
2
2 ，将其中所有活动编号
i
i
i 对应的
a
n
s
[
i
]
ans[i]
ans[i] 设置为
n
u
m
(
2
)
num(2)
num(2) ；依次类推，最后找出最大兼容活动子集个数为
3
3
3 。
对应的完整程序如下：
#include 上述程序的执行结果如下：
【例7.2】求解区间相交问题。
给定
x
x
x 轴上的
n
n
n 个闭区间，去掉尽可能少的闭区间，使得剩下的闭区间都不相交。
对于给定的
n
n
n 个闭区间，计算去掉的最少闭区间数。
输入描述：对于每组输入数据，输入数据的第一行是正整数
n
(
1
≤
n
≤
40000
)
n\ (1 \le n \le 40 000)
n (1≤n≤40000) ，表示闭区间数；在接下来的
n
n
n 行中，每行有两个整数，分别表示闭区间的两个端点。
输出描述：计算出的去掉的最少闭区间数。
输入样例：
3
10 20
15 10
20 15
输出样例：
2
解：采用贪心法求出最大兼容子集，兼容子集中的所有闭区间是不相交的。
设其中的闭区间个数为
a
n
s
ans
ans ，则删除
n
−
a
n
s
n - ans
n−ans 个闭区间得到不相交闭区间。
对应的完整程序如下：
#include 7.3 求解背包问题
【问题描述】设有编号为
1
,
2
,
…
,
n
1, 2, \dots, n
1,2,…,n 的
n
n
n 个物品，它们的重量分别为
w
1
,
w
2
,
…
,
w
n
w_1, w_2, \dots, w_n
w1,w2,…,wn ，价值分别为
v
1
,
v
2
,
…
,
v
n
v_1, v_2, \dots, v_n
v1,v2,…,vn ，其中
w
i
,
v
i
(
1
≤
i
≤
n
)
w_i, v_i\ (1\le i \le n)
wi,vi (1≤i≤n) 均为正数。
有一个背包可以携带的最大重量不超过
W
W
W 。
求解目标是，在不超过背包负重的前提下，使背包装入的总价值最大（即效益最大化）。
与0/1背包问题的区别是，这里的每个物品可以取一部分装入背包。
【问题求解】这里采用贪心法求解。
设
x
i
x_i
xi 表示物品
i
i
i 装入背包的情况，
0
≤
x
i
≤
1
0 \le x_i \le 1
0≤xi≤1 。
根据问题的要求，有如下约束条件和目标函数：
∑
i
=
1
n
w
i
x
i
≤
W
0
≤
x
i
≤
1
,
1
≤
i
≤
n
max
{
∑
i
=
1
n
v
i
x
i
}
\sum^n_{i = 1} w_i x_i \le W\quad 0 \le x_i \le 1, 1 \le i \le n \ \max \bigg \{ \sum^n_{i = 1} v_i x_i \bigg \}
i=1∑nwixi≤W0≤xi≤1,1≤i≤nmax{i=1∑nvixi}
于是问题归结为，寻找一个满足上述约束条件、并使目标函数达到最大的解向量
X
=
(
x
1
,
x
2
,
…
,
x
n
)
X = (x_1, x_2, \dots, x_n)
X=(x1,x2,…,xn) 。
例如，
n
=
3
,
W
=
20
,
(
w
1
,
w
2
,
w
3
)
=
(
18
,
15
,
10
)
,
(
v
1
,
v
2
,
v
3
)
=
(
25
,
24
,
15
)
n = 3, W = 20, (w_1, w_2, w_3) = (18, 15, 10), (v_1, v_2, v_3) = (25, 24, 15)
n=3,W=20,(w1,w2,w3)=(18,15,10),(v1,v2,v3)=(25,24,15) ，其中的四个可行解如下。
在这四个可行解中，第四个解的效益最大，可以求出它是这个输入样例的最优解。
用贪心法求解的关键是如何选定贪心策略，使得按照一定的顺序选择每个物品，并尽可能装入背包，直到背包装满。
至少有三种看似合理的贪心策略。
- 选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。
然而，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。
- 选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。
然而，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。
- 选择单位重量下价值最大的物品，在背包价值增长和背包容量消耗之间寻找平衡。
应用第三种贪心策略，每次从物品集合中，选择单位重量下价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后会面临一个最优子问题——它同样是背包问题，只不过背包容量减少了，物品集合减少了。 因此背包问题具有最优子结构性质
对于表7.2所示的一个背包问题， n = 5 , W = 100 n = 5, W = 100 n=5,W=100 ，其求解过程如下：
- 将价值（即
v
/
w
v / w
v/w ）递减排序，其结果为
(
66
/
30
,
20
/
10
,
30
/
20
,
60
/
50
,
40
/
40
)
(66/30, 20/10, 30/20, 60/50,40/40)
(66/30,20/10,30/20,60/50,40/40) ，物品重新按
1
∼
5
1 \sim 5
1∼5 编号。
- 设背包余下可装入的重量为
w
e
i
g
h
t
weight
weight ，其初值为
W
W
W 。
- 从
i
=
1
i = 1
i=1 开始，
w
[
i
]
<
w
e
i
g
h
t
w[i] < weight
w[i]<weight 成立，表明物品
1
1
1 能够装入，将其装入到背包中，置
x
[
1
]
=
1
,
w
e
i
g
h
t
=
w
e
i
g
h
t
−
w
[
i
]
=
70
x[1] = 1,\ weight =weight- w[i] = 70
x[1]=1, weight=weight−w[i]=70 ，
i
=
i
+
1
=
2
i = i+1 =2
i=i+1=2 。
-
w
[
2
]
<
w
e
i
g
h
t
w[2]
w[2]<weight 成立，表明物品 2 2 2 能够装入，将其装入到背包中，置 x [ 2 ] = 1 , w e i g h t = w e i g h t − w [ 2 ] = 60 x[2] =1,\ weight=weight-w[2] = 60 x[2]=1, weight=weight−w[2]=60 ， i = i + 1 = 3 i = i + 1 = 3 i=i+1=3 。 -
w
[
3
]
<
w
e
i
g
h
t
w[3] < weight
w[3]<weight 成立，表明物品
3
3
3 能够装入，将其装入到背包中，置
x
[
3
]
=
1
,
w
e
i
g
h
t
=
w
e
i
g
h
t
−
w
[
3
]
=
50
x[3] = 1, weight = weight - w[3] = 50
x[3]=1,weight=weight−w[3]=50 ，
i
=
i
+
1
=
4
i = i + 1 = 4
i=i+1=4 。
-
w
[
4
]
<
w
e
i
g
h
t
w[4] < weight
w[4]<weight 不成立，且
w
e
i
g
h
t
>
0
weight > 0
weight>0 ，表明只能将物品
4
4
4 部分装入，装入比例为
w
e
i
g
h
t
w
[
4
]
=
50
60
=
80
%
\dfrac{weight}{w[4]} = \dfrac{50}{60} = 80\%
w[4]weight=6050=80% ，置
x
[
4
]
=
0.8
x[4] = 0.8
x[4]=0.8 ，算法结束，得到
X
=
(
1
,
1
,
1
,
0.8
,
0
)
X = (1, 1, 1, 0.8, 0)
X=(1,1,1,0.8,0) 。
说明：由于每个物品可以只取一部分，因此一定可以让总重量恰好为
W
W
W 。
当物品按价值递减排序后，除最后一个所取的物品可能只取其一部分外，其他物品要么不拿，要么全部拿走。
对应的完整程序如下：
#include 上述程序的执行结果如下：
【算法证明】假设对于
n
n
n 个物品，按
v
i
/
w
i
(
1
≤
i
≤
n
)
v_i / w_i\ (1 \le i \le n)
vi/wi (1≤i≤n) 值递减排序，得到
1
,
2
,
…
,
n
1, 2, \dots, n
1,2,…,n 的序列，即
v
1
/
w
1
≥
v
2
/
w
2
≥
⋯
≥
v
n
/
w
n
v_1 / w_1 \ge v_2 / w_2 \ge \dots \ge v_n / w_n
v1/w1≥v2/w2≥⋯≥vn/wn 。
设
X
=
(
x
1
,
x
2
,
…
,
x
n
)
X = (x_1,x_2, \dots, x_n)
X=(x1,x2,…,xn) 时本算法找到解。
-
如果所有的 x i x_i xi 都等于 1 1 1 ，这个解明显是最优解。
-
否则，设 m i n j minj minj 为满足 x m i n j < 1 x_{minj} < 1 xminj<1 的最小下标。
考虑算法的工作方式，很明显，当 i < m i n j i < minj i<minj 时 x i = 1 x_i = 1 xi=1 ，当 i > m i n j i > minj i>minj 时 x i = 0 x_i = 0 xi=0 ，并且 ∑ i = 1 n w i x i = W \displaystyle \sum^n_{i = 1}w_ix_i = W i=1∑nwixi=W 。
设 X X X 的价值为 V ( X ) = ∑ i = 1 n v i x i V(X) = \displaystyle \sum^n_{i=1}v_ix_i V(X)=i=1∑nvixi 。
设 Y = ( y 1 , y 2 , … , y n ) Y = (y_1, y_2, \dots, y_n) Y=(y1,y2,…,yn) 是该背包问题的一个最优可行解，因此有 ∑ i = 1 n w i y i ≤ W \displaystyle \sum^n_{i=1}w_iy_i \le W i=1∑nwiyi≤W ，从而有 ∑ i = 1 n w i ( x i − y i ) = ∑ i = 1 n w i x i − ∑ i = 1 n w i y i ≥ 0 \sum^n_{i=1}w_i(x_i - y_i) = \sum^n_{i=1}w_ix_i - \sum^n_{i=1}w_iy_i \ge 0 i=1∑nwi(xi−yi)=i=1∑nwixi−i=1∑nwiyi≥0 这个解的价值为 V ( Y ) = ∑ i = 1 n v i y i V(Y) = \displaystyle \sum^n_{i=1}v_iy_i V(Y)=i=1∑nviyi ，则 V ( X ) − V ( Y ) = ∑ i = 1 n v i ( x i − y i ) = ∑ i = 1 n w i v i w i ( x i − y i ) V(X) - V(Y) = \sum^{n}_{i=1}v_i(x_i-y_i) = \sum^n_{i=1}w_i\dfrac{v_i}{w_i}(x_i-y_i) V(X)−V(Y)=i=1∑nvi(xi−yi)=i=1∑nwiwivi(xi−yi)
- 当
i
<
m
i
n
j
i
i<minj 时 x i = 1 x_i = 1 xi=1 ，所以 x i − y i ≥ 0 x_i - y_i \ge 0 xi−yi≥0 ，且 v i / w i ≥ v m i n j / w m i n j v_i / w_i \ge v_{minj} / w_{minj} vi/wi≥vminj/wminj 。 - 当
i
>
m
i
n
j
i > minj
i>minj 时
x
i
=
0
x_i = 0
xi=0 ，所以
x
i
−
y
i
≤
0
x_i - y_i \le 0
xi−yi≤0 ，且
v
i
/
w
i
≤
v
m
i
n
j
/
w
m
i
n
j
v_i / w_i \le v_{minj} / w_{minj}
vi/wi≤vminj/wminj 。
- 当
i
=
m
i
n
j
i = minj
i=minj 时
v
i
/
w
i
=
v
m
i
n
j
/
w
m
i
n
j
v_i /w_i = v_{minj} / w_{minj}
vi/wi=vminj/wminj 。
则有如下证明：
V ( X ) − V ( Y ) = ∑ i = 1 n w i v i w i ( x i − y i ) = ∑ i = 1 m i n j − 1 w i v i w i ( x i − y i ) + ∑ i = m i n j m i n j w i v i w i ( x i − y i ) + ∑ i = m i n j + 1 n w i v i w i ( x i − y i ) ≥ ∑ i = 1 m i n j − 1 w i v m i n j w m i n j ( x i − y i ) + ∑ i = m i n j m i n j w i v m i n j w m i n j ( x i − y i ) + ∑ i = m i n j + 1 n w i v m i n j w m i n j ( x i − y i ) = v m i n j w m i n j ∑ i = 1 n w i ( x i − y i ) ≥ 0 \begin{aligned} &V(X) - V(Y) = \sum^n_{i=1}w_i\dfrac{v_i}{w_i}(x_i-y_i) \ &= \sum_{i=1}^{minj - 1} w_i\dfrac{v_i}{w_i} (x_i - y_i) + \sum_{i=minj}^{minj} w_i\dfrac{v_i}{w_i} (x_i - y_i) + \sum_{i=minj+1}^{n} w_i\dfrac{v_i}{w_i} (x_i - y_i) \ &\ge \sum^{minj-1}_{i=1}w_i\dfrac{v_{minj}}{ w_{minj}} (x_i-y_i) + \sum_{i=minj}^{minj} w_i\dfrac{v_{minj}}{w_{minj}} (x_i - y_i) + \sum_{i=minj+1}^{n} w_i\dfrac{v_{minj}}{w_{minj}} (x_i - y_i) \ &= \dfrac{v_{minj}}{w_{minj}}\sum^n_{i=1} w_i(x_i-y_i) \ge 0 \end{aligned} V(X)−V(Y)=i=1∑nwiwivi(xi−yi)=i=1∑minj−1wiwivi(xi−yi)+i=minj∑minjwiwivi(xi−yi)+i=minj+1∑nwiwivi(xi−yi)≥i=1∑minj−1wiwminjvminj(xi−yi)+i=minj∑minjwiwminjvminj(xi−yi)+i=minj+1∑nwiwminjvminj(xi−yi)=wminjvminji=1∑nwi(xi−yi)≥0这样与 Y Y Y 是最优解的假设矛盾，也就是说，没有哪个可行解的价值会大于 V ( X ) V(X) V(X) ，因此解 X X X 是最优解。
- 当
i
<
m
i
n
j
i
【算法分析】排序算法 sort() 的时间复杂度为
O
(
n
log
2
n
)
O(n\log_2 n)
O(nlog2n) ，while 循环的时间为
O
(
n
)
O(n)
O(n) ，所以本算法的世界复杂度为
O
(
n
log
2
n
)
O(n\log_2 n)
O(nlog2n) 。
说明：背包问题和0/1背包问题类似，所不同的是，在选择物品装入背包时可以选择一部分、而不一定全部装入背包。
这两类问题都具有最优子结构性质，但背包问题可以用贪心法求解，而0/1背包问题却不能用贪心法求解，因为用贪心法求解0/1背包问题，可能得不到最优解。
以表7.2所示的背包问题为例，如果作为0/1背包问题，因为重量为 60 60 60 的物品放不下（此时背包中只余下 50 50 50 重量的物品可放），所以只能舍弃它，选择重量为 40 40 40 的物品，这是一个可行解，但显然不是最优解。
【例7.3】求给定非负整数序列中的数字排列成的最大数字。
例如，给定
{
50
,
2
,
1
,
9
}
\{ 50, 2, 1, 9\}
{50,2,1,9} ，最大数字为
95021
95021
95021 。
说明该算法的思路（179. Largest Number，以及【宫水三叶の相信科学系列】为什么根据「拼接结果的字典序大小」决定「其在序列里的相对关系」是正确的）。
解：采用贪心思路，将数字大的数字排在前面，那么是不是将整数序列递减排序后、从前往后合并就可以了呢？答案是错误的，如果这样做，
{
50
,
2
,
1
,
9
}
\{ 50, 2, 1, 9\}
{50,2,1,9} 递减排序后为
{
50
,
9
,
2
,
1
}
\{ 50, 9, 2, 1\}
{50,9,2,1} ，合并后的结果是
50921
50921
50921 。
应该采用递增的基数排序，再逆序合并原来的数，如图7.4所示。
这里还需要考虑，一个整数是另外一个整数的前缀的特殊情况，如
(
1
,
10
)
(1, 10)
(1,10) ，递增排序后为
(
1
,
10
)
(1, 10)
(1,10)（由于基数排序是稳定的，
1
1
1 排在前面），逆序合并结果是
101
101
101 ，显然是错误的。
所以修改基数排序，当补齐的两个数相同时、让原来位数短的排在后面，以便优先合并，这样
(
1
,
10
)
(1, 10)
(1,10) 递增排序后为
(
10
,
1
)
(10, 1)
(10,1) ，逆序合并结果是
110
110
110 。
这种思路是错误的！如
(
5
,
5001
)
(5, 5001)
(5,5001) ，补齐后为
(
5000
,
5001
)
(5000, 5001)
(5000,5001) ，排序为
(
5
,
5001
)
(5, 5001)
(5,5001) ，得不到最优解。
还可以将各个整数转换为字符串，按字典序递减排序，再顺序合并原来的数（可以证明，没有相同的数字开头时，这种排序方法是对的）。
错误！示例为 s1 = "90", s2 = "9" ，显然 s1 的字典序大于 s_2 ，结果为
909
909
909 、而非最优解
990
990
990 。
因此，修改字典序排序，令一个字符串是另一个的前缀时，短的字符串排在前面。
错误！示例为 s1 = "89", s2 = "8", s3 = "80" ，按字典序排序的结果为
89808
89808
89808 ，按修改的字典序排序的结果为
88980
8 89 80
88980 ，而非最优解
89880
89 8 80
89880 。
正确解法是，按如下方式重载比较函数进行排序：
sort(str.begin(), str.end(), [&](const string &a, const string b) {
return a + b > b + a;
});
【算法证明】对于本问题，所有字符串按上述方法排序后，设字符串为
{
s
1
,
s
2
,
…
,
s
n
}
\{ s_1, s_2, \dots, s_n\}
{s1,s2,…,sn} 。
要证明：若
X
X
X 是这一问题
A
A
A 的最优解，
X
=
{
s
1
}
∪
X
′
X =\{ s_1 \} \cup X'
X={s1}∪X′ ，则
X
′
X'
X′ 是
A
′
=
{
s
2
,
…
,
s
n
}
A' = \{ s_2, \dots, s_n \}
A′={s2,…,sn} 的最优解。
- 首先证明总存在一个以
s
1
s_1
s1 开始的最优解。
假设第一个选中的字符串为 s k ( k ≠ 1 ) s_k\ (k \ne 1) sk (k=1) ，可以构造另一个最优解 Y Y Y ，由于 s 1 + s k > s k + s 1 s_1 + s_k > s_k + s_1 s1+sk>sk+s1 ，所以在 Y Y Y 中调换 s k s_k sk 和 s 1 s_1 s1 ，得到的字符串 Y ′ Y' Y′ 的字典序不小于 Y Y Y（？），有 Y ′ Y' Y′ 也是最优的，这就说明总存在一个以 s 1 s_1 s1 开始的最优解。
- 做出了这一个贪心选择后，原问题就变成了
A
′
A'
A′ 子问题。
此时要证明，如果 X X X 为 A A A 的一个最优解，则 X ′ = X − { s 1 } X' = X - \{ s_1 \} X′=X−{s1} 也是 A ′ A' A′ 的一个最优解。
采用反证法，如果能找到一个 A ′ A' A′ 的字典序更大于 X ′ X' X′ 的解 Y ′ Y' Y′（相当于得到的整数更大），则将 s 1 s_1 s1 加入 Y ′ Y' Y′ 中，就得到一个字符串 s 1 Y ′ s_1Y' s1Y′ ，它的字典序大于 s 1 X ′ s_1X' s1X′ ，这就与 X X X 是最优解的假设矛盾。因此，不存在一个 A ′ A' A′ 的字典序更大的解 Y ′ Y' Y′ ，即 X ′ X' X′ 是 A ′ A' A′ 的最优解。
所以问题 A A A 的最优解 X X X 包含其子问题 A ′ A' A′ 的最优解 X ′ X' X′ ，最优子结构性质得证。
7.4 求解田忌赛马问题
【问题描述】两千年前的战国时期，齐威王与大将田忌赛马。
双方约定每人各出
300
300
300 匹马，并且在上、中、下三个等级中各选一匹进行比赛。
由于齐威王每个等级的马都比田忌的马略强，比赛的结果可想而知。
现在双方各
n
n
n 匹马，依次派出一匹马进行比赛，每一轮获胜的一方将从输的一方得到
200
200
200 银币，平局则不用出钱，田忌已知所有马的速度值、并可以安排出场顺序，问他如何安排比赛获得的银币最多？
输入描述：输入包含多个测试用例，每个用例的第一行是正整数
n
(
n
≤
1000
)
n\ (n \le 1000)
n (n≤1000) ，表示马的数量；后两行分别是
n
n
n 个整数，表示田忌和齐威王的马的速度值。
输入
n
=
0
n = 0
n=0 时结束。
输出描述：每个测试用例输出一行，表示田忌获得的最多银币数。
输入样例：
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
输出样例：
200
0
0
【问题求解】田忌的马的速度用数组
a
a
a 表示，齐威王的马的速度用数组
b
b
b 表示，将
a
,
b
a, b
a,b 数组递增排序。
采用常识性的贪心思路，分以下几种情况：
-
田忌最快的马比齐威王最快的马快，即 a [ r i g h t a ] > b [ r i g h t b ] a[righta] > b[rightb] a[righta]>b[rightb] ，则两者比赛（两个最快的马比赛）田忌赢。
因为此时田忌最快的马一定赢，而选择与齐威王最快的马比赛，对于田忌来说是最优的，如图7.6(a)所示，图中 ■ \blacksquare ■ 表示已经比赛的马， □ \square □ 代表尚未比赛的马，箭头指向的马速度更快。
-
田忌最快的马比齐威王最快的马慢，即 a [ r i g h t a ] < b [ r i g h t b ] a[righta] < b[rightb] a[righta]<b[rightb] ，则选择田忌最慢的马比齐威王最快的马比赛，田忌输。
因为此时齐威王最快的马一定赢，而选择与田忌最慢的马比赛，对于田忌来说是最优的，如图7.6(b)所示。
-
若田忌最快的马与齐威王最快的马的速度相同，即 a [ r i g h t a ] = b [ r i g h t b ] a[righta] = b[rightb] a[righta]=b[rightb] ，又分为以下三种情况：
- 田忌最慢的马比齐威王最慢的马快，即
a
[
l
e
f
t
a
]
>
b
[
l
e
f
t
b
]
a[lefta] > b[leftb]
a[lefta]>b[leftb] ，则两者比赛（两个最慢的马比赛），田忌赢。
因为此时齐威王最慢的马一定输，而选择与田忌最慢的马比赛，对于田忌来说是最优的，如图7.7(a)所示。
- 田忌最慢的马比齐威王最慢的马慢，并且田忌最慢的马比齐威王最快的马慢，即
a
[
l
e
f
t
a
]
≤
b
[
l
e
f
t
b
]
a[lefta] \le b[leftb]
a[lefta]≤b[leftb] 并且
a
[
l
e
f
t
a
]
<
b
[
r
i
g
h
t
b
]
a[lefta] < b[rightb]
a[lefta]<b[rightb]（不等于！），则选择田忌最慢的马与齐威王最快的马比赛，田忌输。
因此此时田忌最慢的马一定输，而选择与齐威王最快的马比赛，对于田忌来说是最优的，如图7.7(b)所示。
- 其他情况，即
a
[
r
i
g
h
t
a
]
=
b
[
r
i
g
h
t
b
]
a[righta] = b[rightb]
a[righta]=b[rightb] 且
a
[
l
e
f
t
a
]
≤
b
[
l
e
f
t
b
]
a[lefta] \le b[leftb]
a[lefta]≤b[leftb] 且
a
[
l
e
f
t
a
]
≥
b
[
r
i
g
h
t
b
]
a[lefta] \ge b[rightb]
a[lefta]≥b[rightb] ，则
a
[
l
e
f
t
a
]
≥
b
[
r
i
g
h
t
b
]
=
a
[
r
i
g
h
t
a
]
a[lefta] \ge b[rightb] = a[righta]
a[lefta]≥b[rightb]=a[righta] ，即
a
[
l
e
f
t
a
]
=
a
[
r
i
g
h
t
a
]
,
b
[
l
e
f
t
b
]
≥
a
[
l
e
f
t
a
]
=
b
[
r
i
g
h
t
b
]
a[lefta] = a[righta],\ b[leftb] \ge a[lefta] = b[rightb]
a[lefta]=a[righta], b[leftb]≥a[lefta]=b[rightb] ，即
b
[
l
e
f
t
b
]
=
b
[
r
i
g
h
t
b
]
b[leftb] = b[rightb]
b[leftb]=b[rightb] ，说明比赛区间的所有马的速度全部相同，任何两匹马比赛都没有输赢。
- 田忌最慢的马比齐威王最慢的马快，即
a
[
l
e
f
t
a
]
>
b
[
l
e
f
t
b
]
a[lefta] > b[leftb]
a[lefta]>b[leftb] ，则两者比赛（两个最慢的马比赛），田忌赢。
从上述过程看出，每种情况对于田忌来说都是最优的，因此最终获得的比赛方案也一定是最优的。
对应的完整程序如下：
#include 7.5 哈夫曼编码
【问题描述】设需要编码的字符集为
{
d
1
,
d
2
,
…
,
d
n
}
\{ d_1, d_2, \dots, d_n\}
{d1,d2,…,dn} ，它们出现的频率为
{
w
1
,
w
2
,
…
,
w
n
}
\{w_1, w_2, \dots, w_n\}
{w1,w2,…,wn} ，应用哈夫曼树，构造最优的不等长的、由
0
,
1
0, 1
0,1 构成的编码方案。
【问题求解】先构建以
n
n
n 个结点为叶子结点的哈夫曼树，然后由哈夫曼树产生「各叶子结点对应字符」的哈夫曼编码。
哈夫曼树 Huffman Tree 的定义：设二叉树具有
n
n
n 个带权值的叶子结点，从根结点到每个叶子结点都有一个路径长度。
「从根结点到各个叶子结点的路径长度」与「相应结点权值」的乘积的和，称为该二叉树的带权路径长度，记作如下形式，其中
w
i
w_i
wi 为第
i
i
i 个叶子结点的权值，
l
i
l_i
li 为第
i
i
i 个叶子结点的路径长度：
WPL
=
∑
i
=
1
n
w
i
×
l
i
\textrm{WPL} = \sum^n_{i=1} w_i \times l_i
WPL=i=1∑nwi×li 由
n
n
n 个叶子结点可以构造出多种二叉树，其中具有最小带权路径长度的二叉树，称为哈夫曼树（也称最优树）。
根据哈夫曼树的定义，一棵二叉树要使其
WPL
\textrm{WPL}
WPL 值最小，必须使权值越大的叶子结点越靠近根结点，而使权值越小的叶子结点越远离根结点。
那么如何构造一棵哈夫曼树呢？其方法如下：
- 由给定的
n
n
n 个权值
{
w
1
,
w
2
,
…
,
w
n
}
\{ w_1, w_2, \dots, w_n\}
{w1,w2,…,wn} 构造
n
n
n 棵只有一个叶子结点的二叉树，从而得到一个二叉树的集合
F
=
{
T
1
,
T
2
,
…
,
T
n
}
F = \{ T_1, T_2, \dots, T_n\}
F={T1,T2,…,Tn} 。
。
- 在
F
F
F 中，选取根结点的权值最小和次小的两棵二叉树作为左右子树，构造一棵新的二叉树，这棵新的二叉树的根结点的权值，为其左、右子树根结点的权值之和，即合并两棵二叉树为一棵二叉树。
- 重复步骤2，直到
F
F
F 中只剩下一棵二叉树时，这棵二叉树就是所要建立的哈夫曼树。
例如，给定
a
∼
e
a \sim e
a∼e 这五个字符，它们的权值集合为
W
=
{
4
,
2
,
1
,
7
,
3
}
W = \{ 4, 2, 1, 7, 3\}
W={4,2,1,7,3} ，构造哈夫曼树的过程如图7.8所示（图中带阴影的结点，表示所属二叉树的根结点）。
利用哈夫曼树构造的、用于通信的二进制编码，称为哈夫曼编码。
在哈夫曼树中，从根到每个叶子都有一条路径，对路径上的各个分支，约定指向左子树根的分支表示
0
0
0 码、指向右子树的分支表示
1
1
1 码，取每条路径上的
0
0
0 或
1
1
1 的序列，作为与各个叶子结点对应的字符的编码，这就是哈夫曼编码。
前面的示例产生的哈夫曼编码如图7.9所示。
每个字符编码由
0
,
1
0, 1
0,1 构成，并且没有一个字符编码是另一个字符编码的前缀（因为字符都在叶子结点上，而不在内部结点上），这种编码称为前缀码，哈夫曼编码是一种最优前缀码。
前缀码可以使译码过程变得十分简单，由于任一个字符的编码都不是其他字符的前缀，从编码文件中不断取出代码某一个字符的前缀码，转换为原字符，即可逐个译出文件中的所有字符。
哈夫曼编码还是一种变长编码，优点在于可以减少编码后的位数，缺点是不能随机解码。
在哈夫曼树的构造过程中，每次都合并两棵根结点权值最小的二叉树，这体现出贪心法的思想。
那么是否可以像前面介绍的算法一样，先按权值递增排序、然后依次构造哈夫曼树呢？由于每次合并两棵二叉树时，都要找最小和次小的根结点，而且新构造的二叉树也参加这一过程，如果每次都排序，这样花费的时间更多，所以绝对不会这样做，而是在已构造的二叉树中，设计一个小根堆来查找最小和次小的根结点（小根堆）。
由
n
n
n 个权值构造的哈夫曼树的总结点个数为
2
n
−
1
2n - 1
2n−1 ，每个结点的二进制编码长度不会超过树高，可以推出这样的哈夫曼树的高度最多为
n
n
n 。
所以用一个数组
h
t
[
0
…
2
n
−
2
]
ht[0\dots 2n-2]
ht[0…2n−2] 存放哈夫曼树，其中
h
t
[
0
…
n
−
1
]
ht[0\dots n-1]
ht[0…n−1] 存放叶子结点，
h
t
[
n
…
2
n
−
2
]
ht[n\dots 2n - 2]
ht[n…2n−2] 存放其他需要构造的结点，
h
t
[
i
]
.
p
a
r
e
n
t
ht[i].parent
ht[i].parent 为该结点的双亲在
h
t
ht
ht 数组中的下标，
h
t
[
i
]
.
p
a
r
e
n
t
=
−
1
ht[i].parent = -1
ht[i].parent=−1 表示它为根结点，
h
t
[
i
]
.
l
c
h
i
l
d
,
h
t
[
i
]
.
r
c
h
i
l
d
ht[i].lchild,\ ht[i].rchild
ht[i].lchild, ht[i].rchild 分别为该结点的左、右孩子的下标。
用 map 容器
h
t
c
o
d
e
htcode
htcode ，存放所有叶子结点的哈夫曼编码，例如 htcode['a'] = "10" 表示字符 'a' 的哈夫曼编码为 10 。
对应的完整程序如下：
#include 上述程序的执行结果如下：
说明：在哈夫曼树的构造中，当合并两棵二叉树时，将两个权值最小和次小的根结点作为左或右孩子均可以，这样构造出的哈夫曼树可能不唯一，因此产生的哈夫曼编码也不唯一，但它们的 WPL \textrm{WPL} WPL 一定是唯一的。
例如，上述程序的执行结果和图7.9所示的哈夫曼编码不同，但都是正确的哈夫曼编码， WPL \textrm{WPL} WPL 均为 36 36 36 。
【算法证明】先讨论两个命题及其证明过程。
-
命题1：两个最小权值字符对应的结点 x x x 和 y y y ，必须是哈夫曼树中最深的两个结点、且它们互为兄弟（从而做出计算最优树的一步贪心选择）。
证明：假设 x x x 结点在哈夫曼树（最优树）中不是最深的，那么存在一个结点 z z z ，有 w z > w x w_z > w_x wz>wx ，但它比 x x x 深，即 l z > l x l_z > l_x lz>lx ，此时结点 x x x 和 z z z 的带权和为 w x × l x + w z × l z w_x \times l_x + w_z \times l_z wx×lx+wz×lz 。如果交换 x x x 和 z z z 结点的位置，其他不变，如图7.10所示，则交换后的带权和为 w x × l z + w z × l x w_x \times l_z + w_z \times l_x wx×lz+wz×lx ，则有 w x × l z + w z × l x < w x × l x + w z × l z w_x \times l_z + w_z \times l_x < w_x \times l_x + w_z \times l_z wx×lz+wz×lx<wx×lx+wz×lz 。
这是因为 w x × l z + w z × l x − ( w x × l x + w z × l z ) = w x ( l z − l x ) − w z ( l z − l x ) = ( w x − w z ) ( l z − l x ) < 0 w_x \times l_z + w_z \times l_x - (w_x \times l_x + w_z \times l_z) = w_x(l_z - l_x) - w_z(l_z - l_x) = (w_x - w_z) (l_z - l_x) < 0 wx×lz+wz×lx−(wx×lx+wz×lz)=wx(lz−lx)−wz(lz−lx)=(wx−wz)(lz−lx)<0（由前面所设有 w z > w x w_z > w_x wz>wx 和 l z > l x l_z > l_x lz>lx ）。这与交换前的树是最优树的假设矛盾，所以上述命题成立。
-
命题2：设 T T T 是字符集 C C C 对应的一棵哈夫曼树，结点 x , y x, y x,y 是兄弟，它们的双亲为 z z z ，如图7.11所示，显然有 w z = w x + w y w_z = w_x + w_y wz=wx+wy 。
现删除结点 x , y x, y x,y ，让 z z z 变为叶子结点，那么这棵新树 T 1 T_1 T1 一定是字符集 C 1 = C − { x , y } ∪ { z } C_1 = C - \{ x, y\} \cup \{ z\} C1=C−{x,y}∪{z} 的最优树。
证明：设 T T T 和 T 1 T_1 T1 的带权路径长度分别为 WPL ( T ) \textrm{WPL}(T) WPL(T) 和 WPL ( T 1 ) \textrm{WPL}(T_1) WPL(T1) ，则有 WPL ( T ) = WPL ( T 1 ) + w x + w y \textrm{WPL}(T) = \textrm{WPL}(T_1) + w_x + w_y WPL(T)=WPL(T1)+wx+wy 。这是因为 WPL ( T 1 ) \textrm{WPL}(T_1) WPL(T1) 含有 T T T 中除 x , y x, y x,y 以外的所有叶子结点的带权路径长度和，另外加上 z z z 的带权路径长度。
假设 T 1 T_1 T1 不是最优的，则存在另一棵树 T 2 T_2 T2 ，有 WPL ( T 2 ) < WPL ( T 1 ) \textrm{WPL}(T_2) < \textrm{WPL}(T_1) WPL(T2)<WPL(T1) 。
由于结点 z ∈ C 1 z \in C_1 z∈C1 ，则 z z z 在 T 2 T_2 T2 中一定是一个叶子结点。
若将 x , y x, y x,y 加入 T 2 T_2 T2 中作业结点 z z z 的左、右孩子，则得到表示字符集 C C C 的前缀树 T 3 T_3 T3 ，如图7.12所示，则有 WPL ( T 3 ) = WPL ( T 2 ) + w x + w y \textrm{WPL}(T_3) = \textrm{WPL}(T_2) + w_x + w_y WPL(T3)=WPL(T2)+wx+wy 。
由前面的几个式子看到 WPL ( T 3 ) = WPL ( T 2 ) + w x + w y < WPL ( T 1 ) + w x + w y = WPL ( T ) \textrm{WPL}(T_3) = \textrm{WPL} (T_2) + w_x + w_y < \textrm{WPL}(T_1) + w_x + w_y = \textrm{WPL}(T) WPL(T3)=WPL(T2)+wx+wy<WPL(T1)+wx+wy=WPL(T) 。这与 T T T 是 C C C 的哈夫曼树的假设矛盾，本命题即证。
-
命题一说明，该算法满足贪心选择性质，即通过合并来构造一棵哈夫曼树的过程，可以从合并两个权值最小的字符开始。
命题二说明，该算法满足最优子结构性质，即该问题的最优解包含其子问题的最优解。
所以采用哈夫曼算法产生的树一定是一棵最优树。
【算法分析】由于采用小根堆，从堆中删除两个结点（权值最小的两个二叉树根结点）、和加入一个新结点的时间复杂度都是
O
(
log
2
n
)
O(\log_2 n)
O(log2n) ，所以构造哈夫曼树算法的时间复杂度为
O
(
n
log
2
n
)
O(n \log_2 n)
O(nlog2n) 。
生成哈夫曼编码的算法循环
n
n
n 次，每次生成路径恰好是一个叶子结点到根结点的路径，平均高度为
O
(
log
2
n
)
O(\log_2 n)
O(log2n) ，所以由哈夫曼树生成哈夫曼编码的算法的时间复杂度也是
O
(
n
log
2
n
)
O(n\log_2 n)
O(nlog2n)（其实也可以
O
(
n
)
O(n)
O(n) 生成）。
【例7.4】有一个英文句子 str="The following code computes the intersection of two arrays." ，统计其中各个字符出现的次数，以其为频度、构造对应的哈夫曼编码，将该英文句子进行编码、得到 enstr ，然后将 enstr 解码为 destr 。
编写程序实现上述功能。
解：首先统计 str 中各个字符出现的次数，用 map 容器 mp 存放。
采用上述原理构造哈夫曼树
h
t
ht
ht ，继而产生对应的哈夫曼编码
h
t
c
o
d
e
htcode
htcode 。
扫描 str ，将字符 str[i] 用 htcode[str[i]] 替换得到编码 enstr 。
在对 enstr 解码时，扫描 enstr 的0/1字符串，从哈夫曼树的根结点开始匹配，当找到叶子结点时，用该叶子结点的字符替代匹配的0/1字符串，即可得到解码字符串 destr 。
对应的完整程序如下：
#include 上述程序的执行结果如下：
说明：从这里看出，编码字符串 enstr 的长度（
244
244
244 个字符）远远大于 str（
59
59
59 个字符），在实际应用中可以用位图存放，这样可以将 enstr 压缩为
244
/
8
=
31
244/8=31
244/8=31 个字符。
7.6 求解流水作业调度问题
流水作业调度问题的描述见5.9节，采用回溯法求解，在6.5节中采用优先队列式分枝限界法求解，这里采用贪心法求解。
【问题求解】采用归纳思路。
- 当只有一个作业
(
a
1
,
b
1
)
(a_1, b_1)
(a1,b1) 时，显然最少时间
T
min
=
a
1
+
b
1
T_{\min} = a_1 + b_1
Tmin=a1+b1 。
- 当有两个作业
(
a
1
,
b
1
)
(a_1,b_1)
(a1,b1) 和
(
a
2
,
b
2
)
(a_2, b_2)
(a2,b2) 时，若
(
a
1
,
b
1
)
(a_1, b_1)
(a1,b1) 在前、
(
a
2
,
b
2
)
(a_2, b_2)
(a2,b2) 在后执行，有如图7.13所示的两种情况，图7.13(a)求出最少时间
T
min
=
a
1
+
b
1
+
a
2
+
b
2
−
b
1
(
b
1
<
a
2
)
T_{\min} = a_1 + b_1 + a_2+b_2 - b_1\ (b_1 < a_2)
Tmin=a1+b1+a2+b2−b1 (b1<a2) ，图7.13(b)求出最少时间
T
min
=
a
1
+
b
1
+
a
2
+
b
2
−
a
2
(
a
2
<
b
1
)
T_{\min} = a_1 + b_1 + a_2 + b_2 - a_2\ (a_2< b_1)
Tmin=a1+b1+a2+b2−a2 (a2<b1) 。
合并起来， T min = a 1 + b 1 + a 2 + b 2 − min ( a 2 , b 1 ) T_{\min} = a_1 +b_1+a_2+b_2 -\min(a_2, b_1) Tmin=a1+b1+a2+b2−min(a2,b1) 。
若 ( a 2 , b 2 ) (a_2, b_2) (a2,b2) 在前、 ( a 1 , b 1 ) (a_1, b_1) (a1,b1) 在后执行，可以求出最少时间 T min = a 2 + b 2 + a 1 + b 1 − min ( b 2 , a 1 ) T_{\min} = a_2 + b_2 + a_1 + b_1 - \min(b_2, a_1) Tmin=a2+b2+a1+b1−min(b2,a1) 。
将两种执行顺序合并起来，有： T min = a 1 + b 1 + a 2 + b 2 − max ( min ( a 2 , b 1 ) , min ( a 1 , b 2 ) ) T_{\min} = a_1 + b_1 + a_2 + b_2 - \max(\min(a_2, b_1), \min(a_1, b_2)) Tmin=a1+b1+a2+b2−max(min(a2,b1),min(a1,b2)) 归纳起来，对于两个作业 ( a 1 , b 1 ) (a_1,b_1) (a1,b1) 和 ( a 2 , b 2 ) (a_2, b_2) (a2,b2) ，若 min ( a 1 , b 2 ) ≤ min ( a 2 , b 1 ) \min(a_1, b_2) \le \min(a_2, b_1) min(a1,b2)≤min(a2,b1) ，则 ( a 1 , b 1 ) (a_1, b_1) (a1,b1) 放在 ( a 2 , b 2 ) (a_2, b_2) (a2,b2) 前面执行；反之，若 min ( a 1 , b 2 ) ≥ min ( a 2 , b 1 ) \min(a_1, b_2) \ge \min(a_2, b_1) min(a1,b2)≥min(a2,b1) ，则 ( a 2 , b 2 ) (a_2, b_2) (a2,b2) 放在 ( a 1 , b 1 ) (a_1, b_1) (a1,b1) 前面执行 ■ \blacksquare ■ 。
由此可得到一个贪心选择的性质，对于给定的作业 ( a , b ) (a, b) (a,b) ：
- 当
a
≤
b
a \le b
a≤b 时，让这类作业中
a
a
a 比较小的作业尽可能先执行。
原因是，假设 a 1 ≤ a 2 a_1 \le a_2 a1≤a2 ，且 a 1 ≤ b 1 , a 2 ≤ b 2 a_1 \le b_1, a_2 \le b_2 a1≤b1,a2≤b2 ，则 a 1 ≤ b 2 a_1 \le b_2 a1≤b2 ，从而 min ( a 1 , b 2 ) = a 1 ≤ min ( a 2 , b 1 ) \min(a_1, b_2) = a_1 \le \min(a_2, b_1) min(a1,b2)=a1≤min(a2,b1) 。
因此， ( a 1 , b 1 ) (a_1, b_1) (a1,b1) 先执行。
- 当
a
>
b
a > b
a>b 时，让这类作业中
b
b
b 比较小的作业尽可能后执行。
原因是，假设 b 1 > b 2 b_1> b_2 b1>b2 ，且 a 1 > b 1 , a 2 > b 2 a_1 > b_1, a_2 > b_2 a1>b1,a2>b2 ，则 a 1 > b 2 a_1 > b_2 a1>b2 ，从而 min ( a 1 , b 2 ) = b 2 < min ( a 2 , b 1 ) \min(a_1, b_2) = b_2 < \min(a_2, b_1) min(a1,b2)=b2<min(a2,b1) 。
因此， ( a 2 , b 2 ) (a_2, b_2) (a2,b2) 后执行。
Johnson算法就是采用这种贪心思路。
其步骤如下：
- 把所有作业按
M
1
,
M
2
M_1, M_2
M1,M2 的执行时间分为两组，
a
[
i
]
≤
b
[
i
]
a[i] \le b[i]
a[i]≤b[i] 对应第一组
N
1
N_1
N1 ，
a
[
i
]
>
b
[
i
]
a[i] > b[i]
a[i]>b[i] 对应第二组
N
2
N_2
N2 。
- 把
N
1
N_1
N1 的作业按
a
[
i
]
a[i]
a[i] 递增排序，
N
2
N_2
N2 的作业按
b
[
i
]
b[i]
b[i] 递减排序。
- 按顺序先执行
N
1
N_1
N1 的作业，再执行
N
2
N_2
N2 的作业，得到的就是耗时最少的最优调度方案。
上面有个问题：先执行
N
2
N_2
N2 、再执行
N
1
N_1
N1 不行吗？事实上，我们从
■
\blacksquare
■ 处可以发现，如果将其写成比较函数、并对所有作业排序，则
N
1
N_1
N1 必然排在
N
2
N_2
N2 前面。
具体来说，令作业
(
a
1
,
b
1
)
,
(
a
2
,
b
2
)
(a_1, b_1), (a_2, b_2)
(a1,b1),(a2,b2) ，前者属于
N
1
(
a
1
≤
b
1
)
N_1\ (a_1 \le b_1)
N1 (a1≤b1) ，后者属于
N
2
(
a
2
>
b
2
)
N_2\ (a_2 > b_2)
N2 (a2>b2) 。
于是分情况比较讨论：
-
a
1
>
a
2
a_1 > a_2
a1>a2 ：可知
b
1
≥
a
1
>
a
2
>
b
2
b_1 \ge a_1 > a_2 > b_2
b1≥a1>a2>b2 ，于是
min
(
a
1
,
b
2
)
=
b
2
<
min
(
a
2
,
b
1
)
=
a
2
\min(a_1, b_2) = b_2 < \min(a_2, b_1) = a_2
min(a1,b2)=b2<min(a2,b1)=a2 ，所以
(
a
1
,
b
1
)
(a_1, b_1)
(a1,b1) 先执行。
-
a
1
≤
a
2
a_1 \le a_2
a1≤a2 ：可知
a
1
≤
min
(
a
2
,
b
1
)
a_1 \le \min(a_2, b_1)
a1≤min(a2,b1) ，因此要判断元素
a
1
,
b
2
a_1, b_2
a1,b2 谁更小。
- 若
a
1
≤
b
2
a_1 \le b_2
a1≤b2 ，则
min
(
a
1
,
b
2
)
=
a
1
≤
min
(
a
2
,
b
1
)
\min(a_1, b_2) = a_1 \le \min(a_2, b_1)
min(a1,b2)=a1≤min(a2,b1) ，所以
(
a
1
,
b
1
)
(a_1, b_1)
(a1,b1) 先执行。
- 若
a
1
>
b
2
a_1 > b_2
a1>b2 ，则
min
(
a
1
,
b
2
)
=
b
2
<
min
(
a
2
,
b
1
)
\min(a_1, b_2) = b_2 < \min(a_2, b_1)
min(a1,b2)=b2<min(a2,b1) ，所以
(
a
1
,
b
1
)
(a_1, b_1)
(a1,b1) 先执行。
- 若
a
1
≤
b
2
a_1 \le b_2
a1≤b2 ，则
min
(
a
1
,
b
2
)
=
a
1
≤
min
(
a
2
,
b
1
)
\min(a_1, b_2) = a_1 \le \min(a_2, b_1)
min(a1,b2)=a1≤min(a2,b1) ，所以
(
a
1
,
b
1
)
(a_1, b_1)
(a1,b1) 先执行。
综合上述种种，我们可以证明，Johnson贪心算法是正确的。
具体实现采用如下结构体数组 c c c ：
int n = 4;
int a[N] = {5, 12, 4, 8}; // 对应M1的时间
int b[N] = {6, 2, 14, 7}; // 对应M2的时间
struct NodeType {
int no; // 作业序号
bool group; // 1代表第一组N1,0代表第二组N2
int time; // a,b的最小时间
bool operator<(const NodeType &s) const {
return time < s.time; // 用于按time递增排序
}
};
扫描
a
,
b
a, b
a,b 数组得到
c
c
c ，对数组
c
c
c 按
t
i
m
e
time
time（
a
,
b
a, b
a,b 的最小值）递增排序。
用一维数组
b
e
s
t
best
best 存放最优调度序列，即将
N
1
N_1
N1 的作业序号按顺序存放在
b
e
s
t
best
best 的前面部分，将
N
2
N_2
N2 的作业序号按反序存放在
b
e
s
t
best
best 的后面部分即可。
注意：因为
N
2
N_2
N2 组中
t
i
m
e
time
time 为
b
b
b 值，按时间递增排序后、对应按
b
b
b 递增排序的结果，要按反序存放到
b
e
s
t
best
best 中、达到按
b
b
b 递减选择作业的目的。
例如，
n
=
4
n = 4
n=4 ，作业的
M
1
M_1
M1 时间
a
[
]
=
{
5
,
12
,
4
,
8
}
a[] = \{ 5, 12, 4, 8\}
a[]={5,12,4,8} ，作业的
M
2
M_2
M2 时间
b
[
]
=
{
6
,
2
,
14
,
7
}
b[] = \{6, 2, 14, 7\}
b[]={6,2,14,7} 。
生成的数组
c
c
c 如表7.5所示，按
t
i
m
e
time
time 排序后的结果如表7.6所示。
再依次扫描数组
c
c
c 的所有元素，将第一组元素按
t
i
m
e
time
time 递增排列放在
b
e
s
t
best
best 的前面部分，将第二组元素（组号为
0
0
0 ）按
t
i
m
e
time
time 递减排列放在
b
e
s
t
best
best 的后面部分，得到的结果如表7.7所示。
此时
b
e
s
t
best
best 中的作业顺序即为最优调度方案，即
3
,
1
,
4
,
2
3, 1, 4, 2
3,1,4,2 。
现在求最优调度下的总时间，用
f
1
f_1
f1 累计
M
1
M_1
M1 上的执行时间（初始时
f
1
=
0
f_1 = 0
f1=0 ），用
f
2
f_2
f2 累计
M
2
M_2
M2 上的执行时间（初始时
f
2
=
0
f_2 = 0
f2=0 ），最终
f
2
f_2
f2 即为最优调度下的消耗总时间。
对于最优调度方案
b
e
s
t
best
best ，用
i
i
i 扫描
b
e
s
t
best
best 的元素，
f
1
f_1
f1 和
f
2
f_2
f2 的计算如下（推导过程见5.9节）：
f
1
=
f
1
+
a
[
b
e
s
t
[
i
]
]
f
2
=
max
(
f
2
,
f
1
)
+
b
[
b
e
s
t
[
i
]
]
\begin{aligned} &f_1 = f_1 + a[best[i]] \ &f_2 = \max (f_2, f_1) + b[best[i]] \end{aligned}
f1=f1+a[best[i]]f2=max(f2,f1)+b[best[i]]
对应的完整程序如下：
#include 上述程序的执行结果如下：
【算法分析】算法的时间主要花费在排序上，所以时间复杂度为
O
(
n
log
2
n
)
O(n\log_2n)
O(nlog2n) ，比采用回溯法和分枝限界法求解更高效。
7.7 求解最优装载问题
【数据结构和算法设计】算法篇(7) 贪心法 多机调度、最优装载问题
7.8 求解多机调度问题
【数据结构和算法设计】算法篇(7) 贪心法 多机调度、最优装载问题
其他题目
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）