【信奥一本通提高篇】基础算法之贪心算法

原文

https://bbs.fmcraft.top/blog/index.php/archives/22/

贪心算法

概述

近年来的信息学竞赛试题，经常出现求一个问题的可行解或最优解的题目。这类问题就是我们通常所说的最优化问题。贪心算法是求解这类问题的一种常用算法。在众多的算法中，贪心算法可以算得上是最接近人们日常思维的一种算法，常被信息学奥赛选手用来求解一些数据规模很大的问题。

一、贪心算法

贪心算法是从问题的初始状态出发，通过若干次的贪心选择而得到的最优值(或较优值)的一种求解问题策略，即贪心策略。
换句话说，贪心策略是一种在每次决策时采取当前意义下最优策略的算法，做出的选择只是在某种约束条件下的局部最优解或较优解，并不一定是全局的最优解或较优解。不过，某些特定的问题是可以利用贪心算法求得其最优解或较优解的。
【引例1】在N行M列的正整数矩阵中，要求从每行中选出一个数，使得选出的N个数的和最大。
分析：本题可以用贪心算法求解。选N次，每一次选出相应行中的最大值即可。
【引例2】在一个N×M的方格阵中，每一格子赋予一个数(即权值),规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权值之和最大。
我们以2×3的矩阵为例：

/	列1	列2	列3
行1	3	4	6
行2	1	2	10
若按贪心算法求解，所得路径为：1→3→4→6。
若按动态规划求解，所得路径为：1→2→ 10→6。
显然，这里用贪心算法求解，得到的并不是问题的最优解。

二、贪心算法的特点

1.贪心选择

所谓贪心选择是指应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每 一步都是当前看似最佳的选择，且这种选择只依赖于已做出的选择，不依赖于未做出的选择。

最优子结构

执行算法时，每一次得到的结果虽然都是当前问题的最优解(即局部最优解),但只有满足全 局最优解包含局部最优解时，才能保证最终得到的结果是最优解。

三、几个简单的贪心实例

1.最优装载问题

给 n 个物体，第i个物体重量为W₁, 选择尽量多的物体，使得总重量不超过C。
【思路点拨】
由于只关心物体的数量，所以装重的没有装轻的划算。只需把所有物体按重量从小到大排 序，依次选择每个物体，直到装不下为止。这就是一种典型的贪心算法，它只顾眼前，但却能得到全 局最优解。
贪心策略：先装最轻的。

2.部分背包问题

有n 个物体，第i个物体的重量为w₁, 价值为 v₁,在总重量不超过C 的情况下让总价值尽量高。 每一个物体可以只取走一部分，价值和重量按比例计算。
【思路点拨】
本题是在上一题的基础上增加了价值项，所以不能简单地像上一题那样先选出轻的(轻的可 能其价值也小),也不能先拿价值大的(它可能特别重),而应该综合考虑两个因素。一种直观的贪心策略是：优先选出价值与重量的比值最大的，直到重量和正好为C。
注意：由于每个物体可以只选出一部分，因此一定可以让总重量恰好为C(或者所有物体全选，总重量还不足C), 而且除了最后一个以外，所有的物体要么不选，要么全部选。
贪心策略：先选出性价比高的。

3.乘船问题

有n个人，第i个人重量为w,。每艘船的载重量均为C,最多可乘两个人。求用最少的船装载所有人的方案。
【思路点拨】
考虑最轻的人i, 他应该和谁一起乘呢?如果每个人都不能和他一起乘，则只能每人乘一艘船。 否则，他应该选择能和他一起乘的人中最重的一个人j。这样的选择只是让“眼前”的浪费最少，因此它是一种贪心策略。
贪心策略：最轻的人和最重的人配对。
这个贪心策略的正确性和有效性是可以用反证法证明的。
证明：假设这个贪心策略不是最优的，最优方案中的i是什么样的呢?
情况1:i不和任何一个人乘同一艘船，那么可以把j拉过来和他一起乘，总船数不会增加(且可能会减少!),并且符合贪心策略。
情况2:i和另外一个人k同乘一艘船，其中k比j轻。把j和k交换后，j原来所在的船仍然不会超重(因为k比j轻),因此i和j同乘一艘船，所得到的新解不会更差，且符合贪心策略。
由此可见，利用本题的贪心策略求解不会丢失最优解。
程序实现。在前面的分析中，比j更重的人只能每人乘一艘船。这样，我们只需用两个指针i和j分别表示当前考虑的最轻的人和最重的人。每次先将指针j往左移动，直到i和j可以共乘一艘船，然后将指针i往右移，指针j往左移，并重复上述操作，直到所有的人都装载上。不难看出，这 个程序的时间复杂度仅为O(n), 是最优算法。

总结

通过以上3个例子，我们大致了解了贪心算法的形式和正确性证明的基本方法。下面，进一步分析几个经典贪心算法的应用，加深对贪心算法的理解。

四、贪心算法的经典应用

1.选择不相交区间问题

给定n个开区间(a,b),选择尽量多个区间，使得这些区间两两没有公共点。
【思路点拨】
首先，按照b_1<=b_2<=…<=b_n,的顺序排序，依次考虑各个区间，如果没有和已经选择的区间冲突，就选：否则就不选。
【正确性】
假设b_1＜b_i且(a_j,b_j)、(a_i,b_i) 分别与之前的区间不冲突，当前选(a_j,b_j).若(a_j,b_j)与(a_j,b_i)不冲突，则还可以选择(a_i,b_i),答案个数加一；若(a_j,b_j)与(a_i,b_i)冲突，因为b_j＜b_i,所以选(a_j,b_j)对以后的影响更小。

2.区间选点问题

【问题描述】
给定n个闭区间[a_i,b_i], 在数轴上选尽量少的点，使得每个区间内都至少有一个点(不同区同内含的点可以是同一个)。
【思路点拨】
首先按照区间的结束位置从小到大排序。然后从区间1到区间n 进行选择：对于当前区间，吾 集合中的数不能覆盖它，则将区间末尾的数加入集合。
贪心策略：取最后一个。
如图下图所示，如果选灰色点，则移动到黑色点会更优。

3.区间覆盖问题

【问题描述】
给n个闭区间[a_i,b_i],选择尽量少的区间覆盖一条指定的线段区间[s,t]。
【思路点拨】
将所有的区间按左端点从小到大排序，依次处理每个区间。每次选择覆盖点s的区间中右端 点坐标最大的一个，并将s更新为该区间的右端点坐标，直到选择的区间已包含了t为止。
贪心策略：在某个时刻的s, 找一个满足a[i]≤s的b[i]最大值即可。

4.流水作业调度问题

【问题描述】
有n个作业要在两台机器M1和M2组成的流水线上完成加工。每个作业i都必须先花时间a在M上加工，然后花时间b在M2上加工。
确定n个作业的加工顺序，使得从作业1在机器M1上加工开始到作业n在机器M2上加工实完为止所用的总时间最短。
【思路点拨】
直观上，最优调度一定让M1、M2的空闲时间尽量短。
Johnson算法：设N1为a＜b的作业集合，N2 为a≥b的作业集合，将N1的作业按a非减序排序，N2中的作业按照b非增序排序，则N1作 业接N2作业构成最优顺序。
算法的程序易于实现，时间复杂度为O(nlogn),正确性需要证明。

5.带限期和罚款的单位时间任务调度

【问题描述】
有n个任务，每个任务都需要1个时间单位执行，任务i的截止时间d_i(1≤d≤n)表示要求任务i在时问d_i结束时必须完成，误时惩罚w_i表示若任务i未在时间d_i结束之前完成，将导致w_i的罚款。
确定所有任务的执行顺序，使得惩罚最少。
【思路点拨】
要使罚款最少.我们显然应尽量完成w[i]值较大的任务。
此时，我们可以将任务按w[i]从大到小进行排序，然后按照排好的顺序依次对任务进行安排。 安排的规则为：使处理任务i的时间既在d[i]之内，又尽量靠后；如果d[i]之内的时间都已经排满，就放弃处理此项任务。
【算法证明】
假设按照上述算法得到的解不是最优的，那么必然存在某个任务j应当安排到处理的过程中 但却没有安排。假设我们要将该任务安排进去，由于在时间d[j]内都已经排满，就必然需要将一个已安排的任务k与之替换，而w[k]≥w[j]。 这样，替换显然会增加罚款的数额、因此，除上还安排方法以外的安排方法都不会使罚款的数额减少，可知用上述算法得到的结果是最优的。
【实现方法】
①先按照罚款数额从大到小快排。
②顺序处理每个任务，若能安排，则找一个最晚时间：否则放在最后的空位上。

练习

如需练习学习的内容，可自行寻找相关题目。
也可以前往FMCRAFT OJ做题。下面的地址可以直接跳转到其相关题目一本通训练中的题单 算法训练中的题单。使用OJ前需要注册账户。