贪心算法详解：从简单到复杂的思维训练
/* 算法深蓝主题 – 算法教程专用 */
什么是贪心算法
💡 贪心算法应用判断
问题是否适合贪心？
✅ 适合贪心
- 具有贪心选择性质
- 具有最优子结构
- 局部最优→全局最优
- 例：活动选择、霍夫曼编码
❌ 不适合贪心
- 需要全局考虑
- 存在后效性
- 局部最优≠全局最优
- 例：01背包、TSP问题
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优选择的算法策略。它不考虑整体最优，只关注局部最优，但在某些问题中，局部最优的累积恰好能得到全局最优解。
贪心算法的核心思想
| 特征 | 说明 | 关键点 |
|---|---|---|
| 局部最优 | 每步都选择当前最好的 | 不回溯，不后悔 |
| 贪心选择性质 | 局部最优能导致全局最优 | 需要证明 |
| 最优子结构 | 问题的最优解包含子问题的最优解 | 递归性质 |
| 无后效性 | 当前选择不影响之前的选择 | 决策独立 |
贪心算法的适用条件
贪心算法 vs 动态规划
| 对比项 | 贪心算法 | 动态规划 |
|---|---|---|
| 决策方式 | 每步做出不可更改的决策 | 考虑所有可能，选择最优 |
| 时间复杂度 | 通常O(nlogn)或O(n) | 通常O(n²)或更高 |
| 空间复杂度 | O(1)或O(n) | O(n)或更高 |
| 正确性 | 需要严格证明 | 一定能得到最优解 |
| 实现难度 | 简单直观 | 相对复杂 |
经典贪心问题详解
1. 活动选择问题
问题描述：有n个活动，每个活动有开始时间和结束时间，选择最多的互不冲突的活动。
贪心策略：优先选择结束时间早的活动。
struct Activity {
int start, end;
bool operator<(const Activity& other) const {
return end < other.end; // 按结束时间排序
}
};
int activitySelection(vector<Activity>& activities) {
sort(activities.begin(), activities.end());
int count = 1; // 第一个活动必选
int lastEnd = activities[0].end;
for (int i = 1; i < activities.size(); i++) {
if (activities[i].start >= lastEnd) {
count++;
lastEnd = activities[i].end;
}
}
return count;
}
2. 霍夫曼编码
问题描述：给定字符出现频率，构造最优前缀编码。
struct Node {
char ch;
int freq;
Node *left, *right;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct Compare {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq; // 小顶堆
}
};
Node* buildHuffmanTree(vector<pair<char, int>>& freqs) {
priority_queue<Node*, vector<Node*>, Compare> pq;
// 创建叶子节点
for (auto& p : freqs) {
pq.push(new Node(p.first, p.second));
}
// 构建霍夫曼树
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
Node* parent = new Node(0, left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 生成编码
void generateCodes(Node* root, string code, map<char, string>& codes) {
if (!root) return;
if (!root->left && !root->right) {
codes[root->ch] = code;
return;
}
generateCodes(root->left, code + "0", codes);
generateCodes(root->right, code + "1", codes);
}
3. 分数背包问题
问题描述：物品可以分割，求背包能装的最大价值。
struct Item {
double weight, value;
double ratio; // 价值密度
bool operator<(const Item& other) const {
return ratio > other.ratio; // 按价值密度降序
}
};
double fractionalKnapsack(vector<Item>& items, double capacity) {
// 计算价值密度并排序
for (auto& item : items) {
item.ratio = item.value / item.weight;
}
sort(items.begin(), items.end());
double totalValue = 0;
for (auto& item : items) {
if (capacity >= item.weight) {
// 完全装入
totalValue += item.value;
capacity -= item.weight;
} else {
// 部分装入
totalValue += capacity * item.ratio;
break;
}
}
return totalValue;
}
4. 最小生成树（Kruskal算法）
struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
class UnionFind {
vector<int> parent, rank;
public:
UnionFind(int n) : parent(n), rank(n, 0) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
bool unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) swap(px, py);
parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
return true;
}
};
int kruskalMST(int n, vector<Edge>& edges) {
sort(edges.begin(), edges.end());
UnionFind uf(n);
int mstWeight = 0;
int edgeCount = 0;
for (auto& edge : edges) {
if (uf.unite(edge.u, edge.v)) {
mstWeight += edge.weight;
edgeCount++;
if (edgeCount == n - 1) break;
}
}
return mstWeight;
}
贪心策略分类
常见贪心策略类型
| 策略类型 | 特点 | 典型问题 | 关键技巧 |
|---|---|---|---|
| 排序贪心 | 先排序再贪心选择 | 活动选择、区间调度 | 选择合适的排序关键字 |
| 交换贪心 | 通过交换证明最优性 | 任务调度、排队问题 | 相邻交换证明 |
| 堆贪心 | 使用优先队列维护最优 | 霍夫曼编码、合并果子 | 动态维护最值 |
| 扫描线贪心 | 从左到右扫描处理 | 区间覆盖、雷达安装 | 维护关键位置 |
| 反悔贪心 | 允许撤销之前的选择 | 任务分配、股票交易 | 使用堆维护可反悔项 |
贪心算法的证明方法
1. 交换论证法
证明思路：假设存在更优解，通过交换操作将其转化为贪心解，证明贪心解不比最优解差。
例题：任务调度
// 有n个任务，第i个任务需要时间t[i]，延迟惩罚为w[i]*完成时间
// 求最小总惩罚
struct Task {
int time, weight;
bool operator<(const Task& other) const {
// 关键：按t/w升序排序
return time * other.weight < other.time * weight;
}
};
long long minPenalty(vector<Task>& tasks) {
sort(tasks.begin(), tasks.end());
long long penalty = 0;
long long currentTime = 0;
for (auto& task : tasks) {
currentTime += task.time;
penalty += task.weight * currentTime;
}
return penalty;
}
2. 反证法
假设贪心策略不是最优的，推出矛盾。
3. 数学归纳法
证明对于规模为n的问题，如果n-1时贪心最优，则n时贪心也最优。
高级贪心技巧
1. 反悔贪心
例题：课程安排
// 每门课有截止时间和持续时间，求最多能完成几门课
struct Course {
int duration, deadline;
bool operator<(const Course& other) const {
return deadline < other.deadline;
}
};
int scheduleCourses(vector<Course>& courses) {
sort(courses.begin(), courses.end());
priority_queue<int> pq; // 大顶堆，存储已选课程的持续时间
int time = 0;
for (auto& course : courses) {
if (time + course.duration <= course.deadline) {
// 可以选这门课
time += course.duration;
pq.push(course.duration);
} else if (!pq.empty() && pq.top() > course.duration) {
// 反悔：用当前课程替换之前最长的课程
time = time - pq.top() + course.duration;
pq.pop();
pq.push(course.duration);
}
}
return pq.size();
}
2. 双指针贪心
// 例题：盛水最多的容器
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int maxWater = 0;
while (left < right) {
int water = min(height[left], height[right]) * (right - left);
maxWater = max(maxWater, water);
// 贪心策略：移动较短的边
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
3. 区间贪心
// 例题：区间覆盖
// 用最少的区间覆盖[0, target]
int minIntervals(vector<pair<int, int>>& intervals, int target) {
sort(intervals.begin(), intervals.end());
int count = 0;
int currentEnd = 0;
int i = 0;
while (currentEnd < target) {
int maxEnd = currentEnd;
// 贪心：选择能覆盖currentEnd且延伸最远的区间
while (i < intervals.size() && intervals[i].first <= currentEnd) {
maxEnd = max(maxEnd, intervals[i].second);
i++;
}
if (maxEnd == currentEnd) return -1; // 无法覆盖
currentEnd = maxEnd;
count++;
}
return count;
}
贪心算法的常见陷阱
错误案例分析
| 问题 | 错误贪心 | 反例 | 正确方法 |
|---|---|---|---|
| 找零钱 | 总是选最大面值 | 面值[1,3,4]，找6元 | 动态规划 |
| 0-1背包 | 按价值密度贪心 | 物品不可分割 | 动态规划 |
| 最短路径 | 每步选最近邻居 | 可能陷入局部最优 | Dijkstra/Floyd |
| 旅行商问题 | 最近邻算法 | NP难问题 | 动态规划/近似算法 |
贪心算法练习题分级
入门级
| 题目 | 贪心策略 | 难度 |
|---|---|---|
| 分发饼干 | 排序匹配 | ★☆☆ |
| 买卖股票 | 累加正收益 | ★☆☆ |
| 跳跃游戏 | 维护最远距离 | ★★☆ |
| 加油站 | 贪心选择加油点 | ★★☆ |
进阶级
| 题目 | 贪心策略 | 难度 |
|---|---|---|
| 会议室安排 | 区间调度 | ★★★ |
| 任务调度器 | 优先队列 | ★★★ |
| IPO项目 | 双堆贪心 | ★★★ |
| 课程表III | 反悔贪心 | ★★★ |
挑战级
| 题目 | 贪心策略 | 难度 |
|---|---|---|
| 最小覆盖子串 | 滑动窗口 | ★★★★ |
| 俄罗斯套娃 | 排序+LIS | ★★★★ |
| 拼接最大数 | 单调栈贪心 | ★★★★ |
| 去除重复字母 | 栈+贪心 | ★★★★ |
贪心算法的优化技巧
1. 预处理优化
// 例：前缀和/后缀和预处理
vector<int> prefixMax(n), suffixMin(n);
prefixMax[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixMax[i] = max(prefixMax[i-1], arr[i]);
}
suffixMin[n-1] = arr[n-1];
for (int i = n-2; i >= 0; i--) {
suffixMin[i] = min(suffixMin[i+1], arr[i]);
}
2. 数据结构优化
- 使用优先队列动态维护最值
- 使用set/map维护有序集合
- 使用并查集处理连通性
- 使用单调栈/队列优化
3. 排序优化
- 多关键字排序
- 自定义比较函数
- 基数排序（特定场景）
贪心算法的应用场景
实际应用
| 领域 | 应用 | 贪心策略 |
|---|---|---|
| 网络路由 | 最短路径 | Dijkstra算法 |
| 数据压缩 | 霍夫曼编码 | 频率贪心 |
| 任务调度 | CPU调度 | 最短任务优先 |
| 资源分配 | 内存管理 | 最佳适应/首次适应 |
| 金融投资 | 投资组合 | 风险收益比 |
总结
贪心算法是算法设计中的重要思想，掌握贪心算法需要：
- 理解本质：局部最优如何导致全局最优
- 识别特征：判断问题是否适合贪心
- 掌握证明：学会证明贪心的正确性
- 积累模式：熟悉常见贪心策略
- 避免陷阱：识别伪贪心问题
- 灵活应用：结合其他算法技巧
记住，贪心算法的精髓在于”贪心的智慧”——知道什么时候该贪，怎么贪，以及为什么这样贪是对的。通过大量练习和思考，你将逐渐培养出贪心算法的直觉！
Views: 0
答复