贪心算法

概念讲解

什么是贪心？

贪心算法是一种在每一步都选择当前最优解的算法策略。

贪心的条件

1. 贪心选择性质： 局部最优能导致全局最优
2. 最优子结构： 问题的最优解包含子问题的最优解

经典模型

1. 活动选择问题

问题： n 个活动，每个有开始和结束时间，求最多能参加多少个活动。

策略： 按结束时间排序，每次选最早结束的。

12345678910111213int activitySelection(vector<pair<int,int>>& activities) {
    sort(activities.begin(), activities.end(), [](auto& a, auto& b) {
        return a.second < b.second;
    });
    int count = 0, lastEnd = 0;
    for (auto& [start, end] : activities) {
        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }
    return count;
}

2. 区间调度问题

策略： 按右端点排序。

3. 分糖果问题

策略： 排序后一一匹配。

考点分析

初赛考查方式

1. 选择题： 贪心策略
2. 程序阅读： 贪心程序
3. 编程题： 贪心应用

常见考点

• 贪心策略设计
• 排序贪心
• 区间问题

例题精讲

例题 1：活动选择

题目： 活动 [(1,3), (2,5), (4,7), (6,8)]，最多能参加几个？

解答：

按结束时间排序：(1,3), (2,5), (4,7), (6,8)

选 (1,3) → (4,7) → 最多 2 个。

例题 2：分糖果

题目： 孩子需求 [1,2,3]，糖果大小 [1,1,3]，最多满足几个？

解答：

排序后匹配：1→1, 2→不满足, 3→3 → 最多 2 个。

练习题

1. 贪心算法的两个条件是什么？

2. 活动选择问题的贪心策略是什么？

3. 贪心和动态规划的区别是什么？

易错点

⚠️ 注意：

1. 贪心不一定能得到最优解
2. 需要证明贪心策略的正确性
3. 排序是贪心的常见预处理
4. 贪心和 DP 的区别：贪心每步选局部最优且不回溯，DP 考虑所有子问题