企业官网建设流程全解析

第三章·贪心算法 第一单元：贪心算法入门——每一步都做出聪明的选择！

同学们，恭喜你们！

经过第二章的学习，你们已经成为一名合格的“暴力枚举小侦探”了。面对一道题，你们知道要列出候选方案、检查条件、避免重复，还学会了用break和剪枝减少不必要的计算。

可是，新的挑战来了！

如果有 1000 个任务、10000 个物品，甚至更多，我们还要把所有方案都列出来吗？

有没有一种办法，不必检查所有可能的方案，而是每次都做一个看起来最划算的选择，最终就能得到好结果？

有！这就是今天的主角——贪心算法（Greedy Algorithm）。

今天，我们要跟随小骑士进入“智慧王国”，完成一连串任务，揭开贪心算法的秘密。

本单元会按照下面的路线展开：

第一站：理解贪心算法

第二站：通过图示一步一步推演

第三站：学习 C++ 基础代码与模板

第四站：用多道例题练习贪心思维

第五站：识别贪心陷阱，知道什么时候不能贪心

第一站：什么是贪心算法？

1. 从分糖果的故事开始

智慧王国举行了一场数学比赛。

国王拿出了 10 颗糖果，分成了三堆，准备奖励给三个小朋友。

现在三个小朋友的想法：

• 小明希望得到尽可能多的糖果；

• 小红希望得到尽可能多的糖果；

• 小刚也希望得到尽可能多的糖果。

国王决定采用一种简单的规则：

按照跑步速度来排队，跑得最快的先挑选那一堆。

小朋友们，按照顺序，每次都是选最多的一堆糖果，这就是最简单的贪心算法，每次要最多。

2. 国王的寻宝之路

小骑士从城堡出发，要沿着道路前进。每走一步，他都可以选择一条接下来能走的路。

每条路旁边都写着一个数字，表示走这条路能获得多少金币。

小骑士决定：

每到一个岔路口，就选择眼前金币最多的那条路。

这就是一个典型的贪心想法：每一步都做出当前看来最好的选择。

但是，这里有一个很重要的提醒：

眼前最好的选择，不一定能带来最终最好的结果。

例如，眼前有一条路可以拿到 10 枚金币，另一条路只能拿到 6 枚金币。但是，拿到 10 枚金币的路后面可能没有其他宝藏，而拿到 6 枚金币的路后面却可能有 100 枚金币。

如果小骑士只看眼前，就可能错过真正的大宝藏。

所以，贪心算法如果就是“每次看到最大的，就拿”：

最后结果未必能够拿的最多，

这说明当前的贪心算法，

未必能够解决所有的问题。

3. 用一句话来看贪心算法

贪心算法：每一步都按照某种规则，选择当前最合适的方案，希望通过一连串选择得到最终答案。

这里的关键词是“当前”和“规则”。

不过，“希望得到最优解”还不够。

在算法竞赛中，我们必须进一步证明：这套规则确实能得到最优解。

第二站：局部最优和全局最优有什么区别？

1. 勇士的迷宫冒险

有一天，勇士来到了一座神秘迷宫。迷宫里有不同的道路，每条道路都需要消耗一定的魔法能量。

勇士的目标是：从起点走到终点，消耗的魔法能量越少越好！

勇士站在起点，发现前面有两条路：

• 道路 A： 眼前只需要消耗 1 点魔法能量，但是走过去以后，后面的道路可能很贵。

• 道路 B： 眼前需要消耗 3 点魔法能量，但是后面可能有一条非常省力的通道。

我们把迷宫简化成下面这张图：

2. 如果只看眼前，会发生什么？

勇士站在起点时，发现：

• 走道路 A，只需要消耗 1 点能量。

• 走道路 B，需要消耗 3 点能量。

如果勇士只看眼前，立刻选择消耗最少的道路 A，那么：

1+9=10

最终消耗 10 点魔法能量。

可是，如果勇士没有只盯着眼前，而是提前考虑整条路线，选择道路 B：

3+2= 5

最终只需要消耗 5 点魔法能量！

所以，眼前最划算的选择，不一定能带来最后最好的结果。

3. 什么是局部最优？什么是全局最优？

局部最优：只看眼前这一步。

勇士发现道路 A 只消耗 1 点能量，于是认为 A 最划算。这是当前这一步的最好选择。

全局最优：看完整个任务的最终结果。

勇士比较了两条完整路线，发现道路 B 的总消耗只有 5 点，因此 B 才是这道题的最优选择。

可以大家记住这句话：

局部最优，看的是眼前一步；全局最优，看的是整个结果。

4. 这和贪心算法有什么关系？

贪心算法的特点，就是每一步都按照某个规则，选择当前看起来最合适的方案。

但要特别注意：

• 贪心算法不是随便做一个眼前最好的选择。

• 我们必须找到一个合适的选择规则。

• 还要判断：按照这个规则一步步选择，最后能不能得到全局最优解。

刚才的迷宫中，如果规则是“每次都选择当前消耗最少的道路”，就可能选错。

因此，并不是所有问题都能用贪心算法解决，也不是所有贪心规则都正确。

但是如果你能找到正确的贪心算法，一般来说，就是解决问题最快速的方法。

第三站：第一个经典贪心问题——怎样安排活动，才能参加得最多？

这一题非常重要！它能帮助我们理解：贪心算法到底应该怎样设计选择规则。

例题 2：魔法学校的活动日

魔法学校举办了一场活动日，小骑士特别想参加尽可能多的活动。

但是，每场活动都有开始时间和结束时间，而且同一时间只能参加一场活动。

学校公布了下面的活动安排：

小骑士应该怎样选择，才能参加尽可能多的活动？

第一步：先尝试一种直觉方法

有人会说：“我们选持续时间最短的活动吧！”

这听起来有道理，因为活动越短，似乎就越容易挤出时间参加其他活动。

但贪心算法不能只凭感觉。我们需要找到一种可靠的选择规则，并分析它为什么有效。

对于经典的“最多参加多少场互不冲突的活动”问题，有一个非常重要的策略：

每次优先选择结束时间最早、且不与已经选择的活动冲突的活动。

为什么是结束时间最早？

因为活动越早结束，就越早腾出时间，给后面的活动留下更多机会。

第二步：按照结束时间排序

原来的活动已经按照结束时间从小到大排列。我们从最前面开始检查。

第三步：一步一步挑选

最后，我们选择了：

一共参加 4 场活动。

这里采用的约定是：一场活动结束后，另一场活动可以立刻开始，即下一场的开始时间不小于上一场的结束时间。

第四步：怎样证明这种规则有效？

我们用直觉来理解：

• 如果第一场选择结束得更晚的活动，那么留给后面活动的时间不会更多；

• 选择结束得最早的活动，可以尽早释放时间；

• 在这个经典活动选择问题中，可以证明：总存在一种最优安排，其第一场活动就是结束时间最早的活动；

• 选定第一场活动后，剩余部分仍然是同样类型的问题，可以继续使用相同规则。

这说明这个问题的贪心策略不是碰运气，而是有理由、有证明的。

注意：这种结论针对的是最多选择互不冲突的活动。如果题目改成“总收益最大”“活动价值最高”，规则就可能完全不同。

第五步：用 C++ 程序来实现

我们需要用结构体把每场活动的开始时间和结束时间绑定起来，再根据结束时间排序。

#include <iostream> #include <algorithm> using namespace std; struct Activity { int start; int finish; }; bool cmp(Activity a, Activity b) { return a.finish < b.finish; } int main() { Activity a[10] = { {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {8, 10}, {8, 11}, {2, 13}, {12, 14} }; sort(a, a + 10, cmp); int cnt = 0; int lastFinish = -1; for (int i = 0; i < 10; i++) { if (a[i].start >= lastFinish) { cout << a[i].start << " " << a[i].finish << endl; cnt++; lastFinish = a[i].finish; } } cout << "最多参加的活动数：" << cnt << endl; return 0; }

输出的活动时间是：

1 4 5 7 8 10 12 14 最多参加的活动数：4

代码里最重要的三句话

第一句：按照结束时间从小到大排序。

sort(a, a + 10, cmp);

第二句：判断当前活动能不能参加。

if (a[i].start >= lastFinish)

第三句：选择活动后，更新上一次活动的结束时间。

lastFinish = a[i].finish;

贪心算法常见的程序结构就是：排序、依次检查、满足条件就选择、更新状态。

第四站：贪心算法题——从简单到进阶

例题 3：用最少的硬币买东西

故事背景

魔法商店里的硬币面值有：

1、5、10

现在小骑士要支付 28 枚金币，想使用尽可能少的硬币。

按照“每次优先拿最大面值硬币”的规则：

1. 拿 2 枚 10，剩余 8；

2. 拿 1 枚 5，剩余 3；

3. 拿 3 枚 1，剩余 0。

总共用了：

2+1+3 = 6 枚硬币

C++ 程序

#include <iostream> using namespace std; int main() { int money = 28; int coin[3] = {10, 5, 1}; int cnt = 0; for (int i = 0; i < 3; i++) { cnt += money / coin[i]; money %= coin[i]; } cout << "硬币总数：" << cnt << endl; return 0; }

输出：

硬币总数：6

代码解释

money / coin[i]

表示当前面值的硬币最多能拿多少枚。

money %= coin[i];

表示拿完这些硬币后，还剩多少钱。

这个贪心策略对这里的硬币面值系统可以得到最优结果，但不能认为任何硬币面值都适合“每次拿最大的”。

接下来就看一个反例。

例题 4：贪心也会失败——换硬币陷阱

假设魔法商店的硬币面值变成：

1、3、4

现在需要支付 6 枚金币。

如果每次都优先拿最大面值硬币：

• 拿 4，剩下 2；

• 拿 1，剩下 1；

• 再拿 1，剩下 0。

总共使用 3 枚硬币。

但是，如果我们拿两枚 3：

3+3 = 6

只需要 2 枚硬币！

这道题是贪心算法的重要反例。

它告诉我们：

不能因为一个策略在某些题目中有效，就认为它在所有题目中都有效。

如果题目要求硬币数量最少，我们需要先确认贪心规则是否正确；如果不能证明，可能要考虑动态规划等其他算法。

例题 5：分配饼干——让尽可能多的小朋友吃饱

故事背景

老师有一些饼干，要分给小朋友。每个小朋友都有一个最低需求：饼干至少达到某个大小，才会满意。

例如：

• 小朋友的需求：1、2、3

• 饼干的大小：1、1、3

每块饼干最多分给一个小朋友，每个小朋友最多拿一块。

目标是：让尽可能多的小朋友满意。

第一步：排序

需求从小到大：

1、2、3

饼干从小到大：

1、1、3

第二步：优先满足需求最小的小朋友

• 需求 1 的小朋友，可以拿大小 1 的饼干；

• 需求 2 的小朋友，剩余的大小 1 不够，跳过；

• 需求 3 的小朋友，可以拿大小 3 的饼干。

最后满足了 2 位小朋友。

参考程序

#include <iostream> #include <algorithm> using namespace std; int main() { int need[3] = {1, 2, 3}; int cookie[3] = {1, 1, 3}; sort(need, need + 3); sort(cookie, cookie + 3); int i = 0; int j = 0; int cnt = 0; while (i < 3 && j < 3) { if (cookie[j] >= need[i]) { cnt++; i++; j++; } else { j++; } } cout << "满意的小朋友人数：" << cnt << endl; return 0; }

输出：

满意的小朋友人数：2

为什么从小需求开始？

因为小需求的孩子可能用小饼干就能满足，不必浪费大饼干。

把大饼干留给需求更大的孩子，有机会满足更多人。

这个例子体现了贪心算法常见的一个技巧：排序后，从最容易处理的对象开始，尽量不浪费资源。

例题 6：排队买票——先服务谁？

故事背景

魔法电影院有 4 位顾客，他们需要的服务时间分别是：

5、1、3、2分钟。

如果每位顾客都必须等前面的人办理完成才能开始服务，怎样安排顺序，才能让所有人的等待时间总和尽可能小？

一种有效策略是：先服务所需时间最短的顾客。

排序后：

1、2、3、5

每个人的等待时间分别为：

• 第一位：0 分钟；

• 第二位：1 分钟；

• 第三位：1 + 2 = 3 分钟；

• 第四位：1 + 2 + 3 = 6 分钟。

等待时间总和：

0+1+3+6 = 10

如果先让需要 5 分钟的顾客办理，其他人就得等更久。

C++ 程序

#include <iostream> #include <algorithm> using namespace std; int main() { int t[4] = {5, 1, 3, 2}; sort(t, t + 4); int wait = 0; int total = 0; for (int i = 0; i < 4; i++) { total += wait; wait += t[i]; } cout << "等待时间总和：" << total << endl; return 0; }

输出：

等待时间总和：10

例题 7：图书馆买书——预算有限，怎样买到最多本？

故事背景

小骑士带着 15 枚金币来到魔法书店，想买尽可能多的书。

书的价格分别是：

7、2、6、4、3

每本书只能买一次。

第一步：思考贪心规则

目标不是买最贵的书，也不是买最有名的书，而是在预算内买到最多本书。

所以，我们应该先考虑价格最便宜的书。

把价格从小到大排序：

2、3、4、6、7

第二步：依次购买

最后买到了 4 本书。

C++ 参考程序

#include <iostream> #include <algorithm> using namespace std; int main() { int price[5] = {7, 2, 6, 4, 3}; int money = 15; int cnt = 0; sort(price, price + 5); for (int i = 0; i < 5; i++) { if (money >= price[i]) { money -= price[i]; cnt++; } else { break; } } cout << "买到的书本数：" << cnt << endl; cout << "剩余金币：" << money << endl; return 0; }

输出：

买到的书本数：4 剩余金币：0

为什么这里可以使用break？

因为价格已经从小到大排序。

如果当前最便宜的未购买书都买不起，那么后面价格更高的书也买不起，所以可以直接结束循环。

这里的break不是随便用的，而是依赖于一个条件：价格已经排好序，并且预算不会增加。

例题 8：给机器安排任务——先完成短任务

故事背景

魔法工厂里有一台机器，要完成 5 个任务。每个任务需要的时间分别是：

6、2、5、1、3

为了尽快完成全部任务，机器应该先做哪个任务？

如果每个任务都必须完整执行完才能开始下一个任务，并且目标是尽早完成全部任务，那么无论顺序如何，总工作时间都是：

6+2+5+1+3 = 17

因此，如果目标只是“全部任务什么时候完成”，排序并不能缩短总工作时间。

但如果目标是“尽可能减少所有任务的平均等待时间”，就可以考虑先做短任务。

这提醒我们：使用贪心之前，一定要明确题目真正优化的是什么。 不要看到任务、时间、排序，就立刻套用“短的先做”。

第五站：贪心算法的基础代码模板

我们已经学了很多例题，我们来把共同的思路整理成模板。

模板一：排序后依次选择

适用于“按照某种顺序处理对象，再判断是否选择”的问题。

#include <iostream> #include <algorithm> using namespace std; int main() { int a[5] = {7, 2, 6, 4, 3}; int n = 5; sort(a, a + n); int cnt = 0; for (int i = 0; i < n; i++) { // 根据题目判断能不能选择 a[i] if (/* 满足选择条件 */) { // 选择 a[i] cnt++; } } cout << cnt << endl; return 0; }

这里的/* 满足选择条件 */是占位说明，不是可以直接运行的完整条件。实际做题时，需要根据题目补上具体判断。

模板二：排序后，使用剩余资源做决定

适用于“预算有限”“容量有限”“资源有限”的问题。

sort(a, a + n); int remain = limit; int cnt = 0; for (int i = 0; i < n; i++) { if (remain >= a[i]) { remain -= a[i]; cnt++; } else { break; } }

其中：

• limit表示最初拥有的资源；

• remain表示剩余资源；

• cnt表示已经选择的对象数量。

这只是一个常见模板。只有当“先选择较小的对象”确实符合题目目标时，才能这样做。

模板三：结构体排序 + 贪心选择

当每个对象有多个属性时，例如活动的开始时间和结束时间，可以使用结构体。

struct Item { int x; int y; }; bool cmp(Item a, Item b) { return a.y < b.y; }

接着：

sort(a, a + n, cmp);

这表示按照y从小到大排序。

如果y表示活动结束时间，那么就可以依次检查结束得更早的活动。

关键不是死记cmp，而是要说清楚：为什么要按照这个属性排序？

第六站：遇到贪心题，怎样判断应该“贪”什么？

同学们，到这里我们已经见过多个贪心策略：

• 活动安排：优先选择结束时间早的活动；

• 换硬币：在特定硬币面值系统中，优先使用大面值硬币；

• 分配饼干：优先满足需求小的小朋友；

• 买书：优先购买便宜的书；

• 排队服务：在优化总等待时间时，优先安排服务时间短的人。

大家可能会问：

有没有一种万能规则，只要按照它做，就能解决所有贪心题？

答案是：没有。

贪心算法最重要的本领，不是“每次选最大”或者“每次选最小”，而是找到与题目目标相匹配的选择规则。

1. 贪心算法的四步思考法

2. 一个很实用的“反例测试法”

当你觉得某个贪心规则很好时，可以先拿特别小的数据测试。

例如，假设我们提出规则：

“只要是找最少硬币，就一定每次拿最大面值的硬币。”

先试试面值：

1、3、4

目标金额：

6

贪心得到：

4+1+1 = 6

用了 3 枚硬币。

但是：

3+3=6

只用了 2 枚硬币。

一个小小的反例，就推翻了“任何硬币系统都可以这样贪心”的说法。

不过要注意：没有找到反例，也不等于已经证明算法正确。 反例测试可以帮助我们发现错误，但要确保算法一定正确，仍然需要严谨的论证。

第七站：课堂闯关——看看你是否真正理解了贪心

挑战 1：选择活动

如果想参加尽可能多场互不冲突的活动，下面哪种规则是经典活动选择问题的正确贪心策略？

A. 优先选择持续时间最长的活动

B. 优先选择结束时间最早且不冲突的活动

C. 优先选择开始时间最晚的活动

挑战 1：正确答案 B

结束得早，能为后续活动留下更多时间。

挑战 2：换硬币

硬币面值是1、3、4，要支付 6 枚金币。每次拿最大面值硬币，能保证使用的硬币数量最少吗？

A. 能，最大面值一定最好

B. 不能，4+1+1 比 3+3 多用一枚硬币

挑战 2：正确答案 B

4+1+1 需要 3 枚，而 3+3 只需要 2 枚。

挑战 3：购买图书

有 10 枚金币，书的价格分别是2、3、6、8。如果目标是买到最多本书，并且每本书只能买一次，优先考虑哪种规则？

A. 优先购买最便宜的书

B. 优先购买最贵的书

C. 优先购买价格最接近 10 的书

挑战 3：正确答案 A

先买便宜的书，可以在预算内尽可能多买几本。

第八站：本单元知识地图与记忆口诀

给同学们留下贪心口诀：

先看目标是什么，再想规则怎么选；

能排序时先排序，选完记得更新状态；

小数据先找反例，想证明后再相信。

最后，再强调一次：贪心算法不是“凭感觉选最好的”，而是找到一条有依据的选择规则，并确保它能解决当前问题。

下一单元，我们将继续学习贪心算法的经典应用：排序与贪心的配合、如何证明贪心策略正确，以及更有挑战性的区间选择问题。