贪心算法综述|Greedy Algorithm

有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学就知道怎么贪。
有人说贪心算法是最复杂的算法，原因也很简单：这世上会贪的人太多了，那轮到你我的份？

贪心算法的设计

基本特点

1. 贪心法常常适用于组合优化问题；
2. 求解过程是多步判断过程，最终的判断序列对应于问题的最优解；
3. 依据某种 “短视的” 贪心选择性质判断，性质好坏决定算法的成败；
4. 贪心法必须进行正确性证明。相反，证明贪心法不正确直接举反例即可.

事实上，在每个贪心算法之下，几乎总有一个更繁琐的动态规划算法。而贪心算法则是在动态规划的结构上，找寻能够通过对当前情况的只一步选择就能化简子问题，并且保证最终解也是最优解的可能。

设计思路

1. 将优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
2. 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
3. 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

得不到最优解

贪心策略不一定得到最优解，在这种情况下可以有两种处理方法:

1. 参数化分析：分析参数取什么值可得到最优解
2. 估计贪心法得到的解在最坏情况下与最优解的误差

一个参数化分析的例子：找零钱问题

正确性证明的方法

事实上，并没有一种适用于所有问题的证明方法，但贪心选择性质和最优子结构是两个关键要素。如果我们能够证明问题具有这些性质，就向贪心算法迈出了重要一步。

此外，充分利用 数学归纳法 也是一种常用的证明方法。

数学归纳法

• 对步数进行归纳
• 交换论证

最大子序和| Maximum Subarray

给定一个整数序列$L=(a_1,a_2,...,a_n)$ ，要求找出一个具有最大和的连续子序列（子序列最少包含一个元素），返回其最大和。

不难写出，最大和的表示：

$$\max_{i,j}\left\{0,\max_{1\leq i\leq j\leq n}\sum_{k=i}^ja_k\right\}$$

• 输入：整数序列$L=(a_1,a_2,...,a_n)$
• 输出：最大和
• 实例：最大子数组和|LeetCode

算法分析

根据问题描述，很容易想到的一种暴力解法是对所给序列的所有可能的子序列进行检查，从而找到满足条件的子序列。很明显这是一个组合优化问题，且采用这种暴力方法很容易产生组合爆炸，时间复杂度很高。

因此应该从问题本身的性质出发，尽量减小计算量。

• 设想当所给数组全为负数时，结果应该是 0；
• 设想从某个子序列最左端开始进行累加，如果结果成了负数，那必然不会比重新找下一个子序列的结果好，所以此时予以丢弃；

根据以上两点，就可以设计贪心算法的伪代码如下：

$$\begin{aligned} &\text{Algorithm: }\;\text{max-subarray}(L)\\\\ 1.&\;sum\leftarrow0\\ 2.&\;result\leftarrow-\infty\\ 3.&\;\mathbf{for}\;i\;=1\;\mathbf{to}\;\text{length}(L)\;\mathbf{do}\\ 4.&\;\qquad sum\leftarrow sum+L[i]\\ 5.&\;\qquad result\leftarrow \text{max}(sum,result)\\ 6.&\;\qquad \mathbf{if}\;sum\lt0\;\mathbf{then}\\ 7.&\;\qquad\qquad sum\leftarrow0\\ 8.&\;\mathbf{return}\;result \end{aligned}$$

注：在 LeetCode 中，该问题并不要求序列全为负数时，结果为0，反而是序列中数值最大的那一位，与上面的问题描述有细微区别

分析得出，该算法的时间复杂度是$O(n)$，空间复杂度是$O(1)$.

算法实现

采用 C++ 进行编程实现，其中假定输入序列是 vector<int> 型数组nums.

int max_subarray(vector<int>& nums) {
	int result = INT_MIN;
	int sum = 0;
	for(int i = 0; i < nums.size(); i++) {
		sum += nums[i];
		result = max(sum,result);
		if (sum < 0) sum = 0;
	}
	return result;
}

测试样例如下所示：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

正确性证明

现考虑利用数学归纳法对该算法的正确性进行证明.

1. 当序列元素只有一个时，根据算法显然能得到最优解；
2. 现假设序列元素个数最大到$k$ 时 ，即$\text{length}(L)\leq k$ 时，算法都能够得到最优解；

假设构成最优解的子序列为$A^*$ ，其位置有3种情况，分别在序列最左端、最右端或者在原序列中间，如下所示：

$[A^*,B_1],[B_2,A^*,B_3],[B_4,A^*]$

在序列$L$ 的末位新增一个元素$x$，使得序列变为$[A,x]$，其中$A$ 是原来规模为$k$ 的序列，此时$\text{length}(L)=k+1$ . 此时的序列也有三种情况：

1. 序列形如：$L=[A^*,B_1,x]$，此时根据算法，相当于对小于$k$ 个规模的序列$[B_1,x]$ 求最优子序列，再将其与$A^*$ 进行比较，显然能够得到最优解;
   （因为算法中有 result=max(result,sum) ）
2. 序列形如：$L=[B_2,A^*,B_3,x]$，显然子序列$B_2$ 的结果不如$A^*$，所以问题退化为和情况一相同；
3. 序列形如：$L=[B_4,A^*,x]$，显然$B_4$ 的结果不如$A^*$，问题在于子序列$[A^*,x]$ 和$A^*$ 的比较上.

现着重考虑情况三.

1. 当$x\leq 0$ 时，$sum(A^*)\leq sum(A^*)+x$ 恒成立，这时算法给出的最优子序列仍是$A^*$，显然成立；
2. 当$x\gt 0$ 时，$sum(A^*)\gt sum(A^*)+x$ 恒成立，这时算法给出的最优子序列是$[A^*,x]$. 下面讨论该情况的正确性。

利用反证法，假设存在一个$B^*$ 在$x\gt0$ 时不包含$x$ 并且又是当前规模为$k+1$，序列形如$L=[B_4,A^*,x]$ 的最优子序列。

我们知道根据贪心算法的划分，$B_4,A^*$ 相邻的元素一定小于0，因为原算法是在 sum<0 之后才重新 sum=0 再划分的。
所以，必然有$sum(B^*)\gt sum(B_4)$，且$A^*\subset B^*$.
又由假设，我们有$x\notin B^*$，所以此时$B^*=A^*$ .
但$sum(A^*)+x\gt sum(A^*)=sum(B^*)$ 恒成立，这与$B^*$ 是最优解矛盾。

综上所述，贪心算法在$k+1$ 时也能够得到最优解，由数学归纳法可得，贪心算法能够得到最优解。

活动选择问题| Activity-selection Problem

给定一个活动( activity )集合$S=\{a_1,a_2,...,a_n\}$.
每一个活动$a_i$ 都有一个开始时间( Start time ) 和 结束时间( Finish time )，分别记为$s_i,f_i$，其中$0\leq s_i,f_i\lt +\infty$.

如果两个活动$a_i,a_j$ 的活动时间不冲突，即$[s_i,f_i)\cap[s_j,f_j)=\varnothing$ 则称二者相互兼容。

要求从满足集合内元素均两两兼容的子集$S_i$ 中，找出最大的兼容活动集$S^*\subset S$，有：

$$|S^*|=\max_{S_i\subset S}|S_i|$$

• 输入：$S,s_i,f_i,\quad i=1,2,...,n$
• 输出：$S^*$

算法分析

考虑对$f_i$ 从小到大进行排序，以最先结束优先的策略进行兼容判断、递归求解，进而选择出一个兼容活动集。该活动集即为所求。

伪代码如下：

$$\begin{aligned} &\text{Algorithm: }\;\text{activity-selector}(S,s,f)\\\\ 1.&\;j\leftarrow1\\ 2.&\;S^*\leftarrow \{a_1\}\\ 3.&\;\mathbf{for}\;i\;=2\;\mathbf{to}\;\text{length}(S)\;\mathbf{do}\\ 4.&\;\qquad \mathbf{if}\;s[i]\geq f[j]\;\mathbf{then}\\ 5.&\;\qquad\qquad S^*\leftarrow S^*\cup\{a_i\}\\ 6.&\;\qquad\qquad j\leftarrow i\\ 7.&\;\mathbf{return}\;S^* \end{aligned}$$

注：该算法之前，假设输入的集合已经按照$f_i$ 从小到大进行排序，即$f_1$ 是$S$ 中最先完成的活动$a_1$.

对上述算法进行分析，不难得出，首先对数据排序花费了$O(n\log n)$ 的时间；
其次，实际处理只有一个循环体，最坏情况下花费$O(n)$ 的时间；
返回结果最大消耗空间$O(n)$.

综上所述，本算法的时间复杂度为$O(n\log n)+O(n)=O(n\log n)$，空间复杂度为$O(n)$.

算法实现

采用 C++ 进行编程实现.

首先构建活动集合的结构体如下：

typedef struct ACTIVITY{
	int index; //活动编号
	int start_time; //活动开始时间
	int finish_time; //活动结束时间
}Activaty;

按照$f_i$ 升序排列：

bool compare(Activaty a, Activaty b){
    return a.finish_time < b.finish_time;
}

注：这将在 .cpp 文件中通过 #include<algorithm> 后调用 sort() 函数实现.

下面是具体算法：

vector<int> activity_selector(Activaty S[],int n){
    // 输入: 活动集，活动个数
    // 输出：最大兼容活动集的索引index集合
    vector<int> A = vector<int>();
    sort(S,S+n,compare);
    A.push_back(S[0].index);
    int j = 0;
    for(int i = 1; i < n; i++){
        if(S[i].start_time >= S[j].finish_time){
            j = i;
            A.push_back(S[i].index);
        }
    }
    return A;
}

测试样例如下所示：

输入：Activaty S[11]={{1,1,4},
                    {2,3,5},
                    {7,6,10},
                    {8,8,11},
                    {9,8,12},
                    {3,0,6},
                    {4,5,7},
                    {5,3,9},
                    {6,5,9},
                    {10,2,14},
                    {11,12,16}};

输出：1 4 8 11

正确性证明

设活动集为$S=\{a_1,a_2,...,a_n\},\forall i,f_i\leq f_{i+1}$
提出命题：由贪心算法执行到第$k$ 步得到的结果$S^{(k)}$ 被最优解$S^*$ 所包含，即$S^{(k)}\subset S^*$.

1. 当$k=1$ 时，假设$S^*$ 中的第一个活动为$a_j\neq a_1$ .
   设$A=(S^*-\{a_j\})\cap \{a_1\}$.
   因为$f_1=\min\limits_{1\leq i \leq n}f_i\leq f_j$，所以替换之后集合依然兼容，且个数不变。因此此时的新集合$A$ 依然是最优解。

2. 现 假设命题成立，证明命题对$k+1$ 的情况也成立。

如下图所示，则$S^*$ 相当于在待选集$S'$ 中选择其最优解$B$，然后与$S^{(k)}$ 相并所得. 即：$S^*=S^{(k)}\cup B$.

其中$S'=\{a_i|s_i\geq \max\limits_{a_j\in S^{(k)}}f_j,a_i\in S,a_i\notin S^{(k)}\}$.
事实上在待选集$S'$ 中找寻最大兼容活动集就是原问题的一个子问题，所以其最优解$B$
必包含$S'$ 中的第一个活动，即结束时间最早的那个活动。

若$B$ 不是最优解，则存在最优解$B^*$ ，使得$|B^*|\gt |B|,|S^{(k)}\cup B^*|\gt |S^*|$.
这与$S^*$ 是整个问题的最优解矛盾。

综上所述，贪心算法执行的每一步都能得到最优解的子集，全部执行完毕之后能直接得到最优解。

最优装载问题| Optimal loading Problem

假定有$n$ 个集装箱分别编号为$1,2,3,...,n$. 第$i$ 个集装箱的重量记为$w_i$.
现需要将尽可能多的集装箱放入轮船进行装载，轮船对集装箱的体积不做要求，但是重量限制为$W$. 本问题要求给出最多能装的集装箱个数，及其编号。

设向量$\boldsymbol x=[x_1,x_2,...,x_n]$ 为解向量，其中$x_i\in\{0,1\}$.

$$x_i=\begin{cases}1,&\text{将编号为 }i\text{ 的集装箱放入轮船}\\ 0,&\text{其它}\end{cases}$$

进而得到优化模型：

$$\begin{aligned} &\max_{\boldsymbol x}\sum_{i=1}^nx_i\\ s.t.&\begin{cases}\sum\limits_{i=1}^{n}w_ix_i\leq W \\x_i=0,1,\quad i=1,2,...,n\end{cases} \end{aligned}$$

• 输入：$w,W$ (此处$w$ 为由各集装箱重量组成的数组)
• 输出：$\max\limits_{\boldsymbol x}\sum\limits_{i=1}^{n}x_i$

算法分析

选择“轻者优先”的贪心策略，直接将重量从小到大进行排序，依次放入轮船，直到不能放为止。伪代码如下：

$$\begin{aligned} &\text{Algorithm: }\;\text{best-loading}(w,W)\\\\ 1.&\;sum\leftarrow0\\ 2.&\;result\leftarrow0\\ 3.&\;\text{sort}(w)\quad//\text{升序排列}w[1..n]\\ 4.&\;\mathbf{for}\;i\;=1\;\mathbf{to}\;\text{length}(w)\;\mathbf{do}\\ 5.&\;\qquad \mathbf{if}\;sum+w[i]\leq W\;\mathbf{then}\\ 6.&\;\qquad\qquad sum\leftarrow sum+w[i]\\ 7.&\;\qquad\qquad result\leftarrow result+1\\ 8.&\;\qquad \mathbf{else}\;\text{exit}\\ 9.&\;\mathbf{return}\;result \end{aligned}$$

注：该伪代码并未给出如何反推出选取的集装箱的编号，事实上这只需在对$w$ 进行排序时记住排序之后的下标即可.

时间复杂度为$O(n\log n)+O(n)=O(n\log n)$，空间复杂度为$O(1)$.

算法实现

采用 c++ 进行编程.

int best_loading(vector<int> &w, int W){
	int sum = 0;
	int result = 0;
	for(int i = 0; i < w.size(); i++){
		if(sum + w[i] <= W){
			sum += w[i];
			result++;
		}else
			break;	
	}
	return result;
}

测试样例如下所示：

输入：[7 5 8 1 5 3 9],16

输出：4

正确性证明

利用数学归纳法.

假设 对于规模为$n$ 的问题，贪心法都能得到最优解。

若输入：$N=\{1,2,...,n,n+1\}$. 其中，$w_1\leq w_2\leq \cdots\leq w_n\leq w_{n+1}$.
则根据假设，对于$N'=N-\{1\},W'=W-w_1$ 这一问题，贪心法可以得到最优解，记为$X'$.

注：此处对于解的定义是包含装入轮船的集装箱编号.
如$X'=\{1,2,3\}$ 表示标号为 1、2、3的集装箱均放入轮船，此时得到最优解。

这里解的结构定义区别于上面用 0-1向量的定义，这也是为了更好地证明问题，并不影响解的正确性.

此时算法对$(N,W)$ 的这个问题，给出的算法解为$X=X'\cup \{1\}$.
于是有$X$ 是该问题的最优解，否则存在最优解$X^*$，使得$|X^*|\gt |X|$ 且$1\notin X^*$.
那么，也有$|X^*-\{1\}|\gt|X-\{1\}|=|X'|$ ，而这与$X'$ 是问题$(N',W')$ 的最优解矛盾。

最小延迟调度| Scheduling to Minimize Lateness

给定一系列工作( Jobs )$\boldsymbol J=[J_1,J_2,...,J_n]$ ，及其对应的截止时间( deadline )$d_i$ 和完成这项工作所需的执行时间$t_i$.

如果第$i$ 个工作的开始执行时间记为$s_i$，则它的完成( finish )时间$f_i=s_i+t_i$.
所以一项工作的延迟 (Lateness) 时间就是$L_i=\max\{0,f_i-d_i\}$.

本问题要求找出这样一个调度( Schedule )$T:\boldsymbol J\to \boldsymbol J'$ 使得延迟最大的那项工作的延迟能在调度的作用下达到最小。即：

$$\begin{aligned} &\min_{T}\{\max_{1\leq i\leq n} L_i\}\\\\ s.t.&\quad s_i+t_i\leq s_{i+1} \end{aligned}$$

• 输入：$\boldsymbol{J,d,t}$，分别表示由工作编号、对应截止时间、对应执行时间组成的数组
• 输出：最迟延迟时间

算法分析

选择 “截止时间早的任务优先” 的贪心策略，选取这样的映射$T:J\to J'$ 使得新的调度中，$d_1\leq d_2\leq \cdots\leq d_n$. 并且要求上一项工作完成后立刻处理下一项工作.

从而直接对这样的调度进行最迟延迟时间的计算，结果即是最优解，伪代码如下：

$$\begin{aligned} &\text{Algorithm: }\;\text{minimize-lateness}(J,d,t)\\\\ &J[1..n]\quad//Jobs\\ &d[1..n]\quad//Deadline\\ &t[1..n]\quad//Processing\;time\\\\ 1.&\;\text{sort }J,t,d\text{ order by }d\text{ so that }d_1\leq d_2\leq \cdots\leq d_n\\ 2.&\;s\leftarrow0\\ 3.&\;endtime\leftarrow0\\ 4.&\;\mathbf{for}\;i\;=1\;\mathbf{to}\;\text{length}(J)\;\mathbf{do}\\ 5.&\;\qquad s\leftarrow s+t[i]\\ 6.&\;\qquad endtime\leftarrow \text{max}(endtime,s-d[i])\\ 7.&\;\mathbf{return}\;endtime \end{aligned}$$

时间复杂度为$O(n\log n)+O(n)=O(n\log n)$，空间复杂度为$O(1)$.

算法实现

首先构建工作任务的结构体如下：

typedef struct JOB{
	int index; 
	int deadline; 
	int process_time;
}Job;

按照$d_i$ 升序排列：

bool compare(Job a, Job b){
    return a.deadline < b.deadline;
}

注：这将在 .cpp 文件中通过 #include<algorithm> 后调用 sort() 函数实现.

下面是具体算法：

int minimize_lateness(Job J[], int n){
    // 输入: 工作任务集，工作任务数
    // 输出：最小延迟时间
    sort(J, J+n, compare);
    int s = 0;
    int result = 0;
    for(int i = 0; i < n; i++){
        s = s+J[i].process_time;
        result = max(result,s-J[i].deadline);
    }
    return result;
}

测试样例如下所示：

输入：Job J[5] = {{1,10,5},
                {2,12,8},
                {3,15,4},
                {4,11,10},
                {5,20,3}};

输出：12

正确性证明

分析上述贪心算法中解的性质可以看出，算法解给出的排序是没有空闲时间也不存在逆序的。
这里对逆序的定义如下：

$$\tau(i,j)=1\quad \text{ where }s_i\gt s_j,\text{ but }d_i\lt d_j$$

这表示，对于某一调度$T:J\to J'$，如果调度后的某两个工作$J_i,J_j$ 对应的截止时间前者优先级高，但是却让后者优先执行，即经调度后的任务排序$\boldsymbol J'$ 中 任务$J_i$ 排在了 任务$J_j$ 后面，出现这种情况的一对$i,j$ ，其逆序数记为1.

为了证明贪心算法的正确性，此处采用交换论证法.

给出 引理 ：所有没有逆序、没有空闲时间的调度具有相同的最大延迟.

证明 假设存在多个没有逆序、没有空闲时间的调度。既然满足这样的调度存在有多个，当且仅当 存在有限个 Jobs$\in \tilde{J}\subset J$，它们的 deadline 都相同，记为$d$.

在这种情况下把这些 Jobs 进行交换才不会影响逆序数，不仅如此它们一定连续排列，因此这系列 Jobs 中的最大延迟就是最后一个 Job 的延迟：$L_{\max}=f_{\text{last job}}-d$. 证毕.

---

假设存在一个最优调度$T'$，那么有以下三种情况：

1. $T'$ 生成的新序列中逆序数$\tau=0$，此时根据引理，$T$ ，即算法解仍是最优解；
2. $T'$ 生成的新序列中存在逆序 ，将证明对其进行调整，使其转化为算法解后，解仍为最优。

要证明情况2，只需利用以下两个要点：

• 要点1：序列存在逆序$\Leftrightarrow$ 序列存在有限个相邻逆序
• 要点2：交换相邻逆序$i,j$ 得到的解仍为最优解

证明 交换相邻任务前后不影响两个任务合在一起后的开始时间和完成时间，即交换行为只会对$i,j$ 的延迟时间产生影响。

如图所示，设两个任务开始时间为$s_0$，则结束时间为$s_0+t_i+t_j$.
对于调度$T_1$，有延迟时间$L(i,j)=(s_0+t_i+t_j)-d_j$；
对于调度$T_2$，有延迟时间$L(j,i)=(s_0+t_i+t_j)-d_i$；
因为$(i,j)$ 是逆序的，所以有$d_i\gt d_j$ ，从而$L(i,j)\gt L(j,i)$。

对于整个问题来说，调度$T_1$ 情况下的最大延迟时间：

$$\max_{T_1} L\geq L(i,j)\gt L(j,i)$$

即交互相邻逆序之后，不影响最大延迟时间。
因此在有限次的交换之后，可以将最优解转化为算法解，仍为最优。

田忌赛马问题

可图性问题

参考资料

1. 《算法导论(原书第三版)》
2. 最大子数组和 - 力扣（LeetCode）
3. 算法设计与分析|中国大学MOOC
4. 使用贪心算法和动态规划团灭活动选择问题
5. Scheduling to Minimize Lateness|伊利诺伊大学课件