【GESP】C++五级考试大纲知识点梳理, (8) 贪心算法

GESP C++五级官方考试大纲中，共有9条考点，本文针对第8条考点进行分析介绍。

（8）掌握贪心算法的基本原理，理解最优子结构，能够使用贪心算法解决相关问题。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

五级其他考点回顾：

• 【GESP】C++五级考试大纲知识点梳理, (1) 初等数论
• 【GESP】C++五级考试大纲知识点梳理, (2) 模拟高精度计算
• 【GESP】C++五级考试大纲知识点梳理, (3-1) 链表-单链表
• 【GESP】C++五级考试大纲知识点梳理, (3-2) 链表-双向链表
• 【GESP】C++五级考试大纲知识点梳理, (3-3) 链表-单向循环链表
• 【GESP】C++五级考试大纲知识点梳理, (3-4) 链表-双向循环链表
• 【GESP】C++五级考试大纲知识点梳理, (4) 辗转相除法、素数表和唯一性定理
• 【GESP】C++五级考试大纲知识点梳理, (5) 算法复杂度估算（多项式、对数）
• 【GESP】C++五级考试大纲知识点梳理, (6) 二分查找和二分答案
• 【GESP】C++五级考试大纲知识点梳理, (7) 递归算法 - 1 基本原理
• 【GESP】C++五级考试大纲知识点梳理, (7) 递归算法 - 2 复杂度分析
• 【GESP】C++五级考试大纲知识点梳理, (7) 递归算法 - 3 优化策略

---

一、什么是贪心算法

“贪心算法”（Greedy Algorithm）顾名思义，就是在问题求解的过程中，每一步都做出当前看来最优的选择，希望通过这些局部最优的选择，最终得到全局最优解。

打个比方：

你走迷宫时，每次都选择“离出口最近的方向”走，这就是一种“贪心策略”。它不回头、不尝试所有路径，只追求“眼前最好”。

贪心算法的核心思想是：

局部最优 → 全局最优（在某些问题中成立）

但注意，并不是所有问题都可以用贪心算法解决，关键在于问题是否满足一定条件。

---

二、贪心算法的两个关键性质

想判断一个问题能否用贪心算法解决，需要满足两个条件：

1. 最优子结构（Optimal Substructure）

问题的最优解可以由它的子问题的最优解构成。 换句话说：

如果我们把问题拆成若干个子问题，那么“整个问题的最优解”一定是由“每个子问题的最优解”拼起来的；只要子问题选得最优，整体就不会因为子问题的选择而变差。

例如： 在最短路径问题（如 Dijkstra 算法） 中，从 A 到 C 的最短路径一定经过 A 到 B 的最短路径——这就是“最优子结构”。

2. 无后效性（Greedy Choice Property）

当前阶段的选择不会影响后续阶段的选择。 换句话说：

一旦我们按照贪心规则做出了某个选择，这个选择就永远不需要被撤销或回退，它不会导致后面“原本可以得到的更优解”变成不可得。

例如： 在活动选择问题中，只要选择当前结束时间最早的活动，就不会影响后面能选择的最多活动数。

---

三、贪心算法的基本思路

贪心算法的一般设计步骤：

1. 确定贪心策略：每一步该如何“贪心”地选择？（比如选最小、选最大、选最早结束的等）
2. 证明可行性：该策略是否能保证全局最优？

3. 实现过程：

   • 按照贪心策略排序；
   • 从头到尾做出选择；
   • 保留满足条件的部分结果；
   • 得出最终解。

---

四、典型例题讲解

例 1：活动选择问题（经典题）

问题描述： 有 $n$ 个活动，每个活动有开始时间 s[i] 和结束时间 f[i]，同一时间只能进行一个活动。求能安排的最多活动数量。

贪心思路：

• 每次选择结束时间最早的活动；
• 然后删除所有与它冲突的活动；
• 重复上述步骤。

伪代码：

sort(activities.begin(), activities.end(), by_finish_time); // 按结束时间升序，最早结束的排在前面
int count = 0, last_end = 0;                // count 记录已选活动数；last_end 记录最近一次选中活动的结束时间
for (auto a : activities) {                 // 依次考察每个活动
    if (a.start >= last_end) {              // 若当前活动开始时间 ≥ 上一个选中活动的结束时间，则无冲突
        count++;                            // 选中该活动
        last_end = a.finish;                // 更新“最后结束时间”为当前活动的结束时间
    }
}
cout << count;                              // 输出最多可安排的活动数量

思维解释： 结束早的活动留出了更多时间给后面的活动，从全局角度看最优。 这道题同时具备“最优子结构”和“无后效性”，所以贪心算法成立。

---

例 2：找零钱问题

问题描述： 有 1、5、10、50、100 元面值的硬币，要求找出最少硬币数凑成金额 n。

贪心思路： 每次都取当前能用的最大面值硬币。

示例： 要凑 136 元：

• 先取 1 张 100 元（剩 36）；
• 再取 1 张 10 元（剩 26）；
• 再取 2 张 10 元（剩 6）；
• 再取 1 张 5 元（剩 1）；
• 再取 1 张 1 元。 → 共 6 枚硬币。

伪代码：

int coins[] = {100, 50, 10, 5, 1}; // 硬币面值从大到小排列，保证贪心策略正确
int n, cnt = 0;                   // n 为待凑金额，cnt 记录硬币总数
cin >> n;                         // 读入需要凑出的金额
for (int i = 0; i < 5; i++) {     // 遍历每种面值
    cnt += n / coins[i];        // 当前面值能用多少枚就用多少枚
    n %= coins[i];                // 凑完以后剩下的金额
}
cout << cnt;                      // 输出最少硬币数量

注意：
并不是所有货币系统都适合贪心策略。
例如面值为 {1, 3, 4} 时，要凑 6：

• 贪心取 4 + 1 + 1（3 枚）
• 但最优解是 3 + 3（2 枚） 所以，贪心算法并非万能！

---

例 3：哈夫曼编码（Huffman Coding）

问题描述： 给定若干字符及其出现频率，要求设计一套二进制前缀编码（即没有任何一个编码是另一个编码的前缀），使得所有字符的总编码长度（频率 × 编码长度）最小。例如，字符集 {A,B,C,D} 对应频率 {5,2,1,2}，若采用变长编码 A→0、B→10、C→110、D→111，则总编码长度为 5×1 + 2×2 + 1×3 + 2×3 = 18 位，比等长编码更节省空间。

题目拆解：

根据题目要求，我们要给每个字符安排一个唯一的 0/1 串，保证没有一个串是另一个串的“开头”，并且让“出现次数多的字符尽量短、出现次数少的字符可以稍长”，最终把所有字符的“出现次数×编码长度”加起来，整体最短——这正是贪心思想在压缩领域的经典落地：每一步都“贪”频率最高的字符，让它离根最近，从而把总代价压到最低。

贪心思路：

构造一棵树：

• 树的叶子 = 每个字符
• 树的路径长度 = 编码长度
• 树的权重 = 字符出现频率
• 目标 = 让高频字符更靠近根（路径短），低频字符更靠下（路径长）

构造过程：

• 把所有字符看成“只有根节点”的小树，每棵树的权重就是该字符的出现频率；
• 每次从“森林”里选出频率最小的两棵树，把它们合并成一棵新树：新树的根节点频率 = 左子树频率 + 右子树频率，且频率小的放在左边，大的放在右边（左右顺序不影响正确性，但统一规则便于编码）；
• 重复上述“选最小、合并”动作，直到只剩下一棵树为止；
• 最终得到的唯一二叉树就是哈夫曼树：从根到每个叶子节点的路径，左走记 0，右走记 1，就能得到总长度最短的前缀编码。

构造过程示意：

第 1 步：

频率最小的两个字符是：

C(1)，B(2)

合并成一个新节点：

      (3)
     /   \
   (1)   (2)
   C      B

现在剩下的节点：A(5)，D(2)，新节点(3)

第 2 步：

最小的两个是 D(2) 和 (3)

合并：

        (5)
       /   \
     (2)   (3)
     D     [CB]

剩余：A(5)，(5)

---

第 3 步：

合并最后两个 5：

          (10)
         /    \
      (5)     (5)
     A       [D,CB]

---

完整哈夫曼树示意图

            (10)
           /    \
        (5)     (5)
       A       /  \
            (2)    (3)
            D     /   \
                 C     B

编码生成（左0右1）

从根节点出发：

• 左分支记 0
• 右分支记 1

于是：

字符	编码路径	编码	频率×长度
A	左	0	5×1 = 5
D	右→左	10	2×2 = 4
C	右→右→左	110	1×3 = 3
B	右→右→右	111	2×3 = 6

总长度 = 5 + 4 + 3 + 6 = 18 位。

---

五、贪心算法的优缺点

优点	缺点
实现简单、效率高（通常 $O(n \log n)$）	不能保证所有问题最优解
思路直观、易于编码	需要严格证明贪心选择的正确性

---

六、总结：如何判断能否用贪心算法？

当你遇到一道题时，可以按以下思路判断：

1. 是否存在明显的局部选择策略？（如最早结束、最小代价、最大收益）
2. 这种策略会不会影响后续选择？（满足无后效性）
3. 局部最优能否组合成整体最优？（满足最优子结构）

如果条件都满足，就可以尝试用贪心算法。

✅ 一句话总结：

贪心算法是一种在每一步都做局部最优选择、并希望由此导出全局最优解的算法策略。掌握“最优子结构”和“无后效性”，就能学会用贪心的眼光解决问题。

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号