贪心算法入门：从经典问题到实战技巧
贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法思想。本文基于算法入门培训第二讲的内容，系统总结贪心算法的核心概念、经典问题以及实现技巧。
1. 贪心算法基本思想
贪心算法的核心思想是：在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
贪心算法的特点：
- 局部最优选择：每一步都选择当前最优解
- 不可回溯：一旦做出选择就不可更改
- 高效性：通常时间复杂度较低
- 不保证全局最优：在某些问题中可能无法得到全局最优解
2. 经典贪心问题解析
2.1 硕鼠的交易问题
问题描述：老鼠有M单位猫粮，要与N只猫交易。每个猫房间有J[i]单位豆子，需要F[i]单位猫粮。可以按比例交易，求最多能获得多少豆子。
贪心策略：按性价比（豆子/猫粮）从高到低排序，优先交易性价比高的房间。
struct Room {
double javaBeans; // 豆子数量
double catFood; // 所需猫粮
double ratio; // 性价比
};
bool cmp(Room a, Room b) {
return a.ratio > b.ratio; // 按性价比降序排列
}
double maxJavaBeans(Room rooms[], int n, double m) {
sort(rooms, rooms + n, cmp);
double result = 0.0;
for (int i = 0; i < n && m > 0; i++) {
if (m >= rooms[i].catFood) {
result += rooms[i].javaBeans;
m -= rooms[i].catFood;
} else {
result += rooms[i].javaBeans * (m / rooms[i].catFood);
m = 0;
}
}
return result;
}
2.2 田忌赛马问题
问题描述：田忌和齐王各有N匹马，马的速度不同。每场比赛胜者得200银币，负者输200银币。求田忌最多能赢多少钱。
贪心策略：
- 将双方马匹按速度排序
- 比较双方最快的马：
- 田忌最快的马 > 齐王最快的马：直接比赛，田忌赢
- 田忌最快的马 < 齐王最快的马：用田忌最慢的马与齐王最快的马比赛，减少损失
- 速度相等时：比较最慢的马
int tianjiHorseRacing(int tianji[], int king[], int n) {
sort(tianji, tianji + n);
sort(king, king + n);
int tianjiFast = n - 1, kingFast = n - 1;
int tianjiSlow = 0, kingSlow = 0;
int result = 0;
for (int i = 0; i < n; i++) {
if (tianji[tianjiFast] > king[kingFast]) {
result += 200;
tianjiFast--;
kingFast--;
} else if (tianji[tianjiFast] < king[kingFast]) {
result -= 200;
tianjiSlow++;
kingFast--;
} else {
if (tianji[tianjiSlow] > king[kingSlow]) {
result += 200;
tianjiSlow++;
kingSlow++;
} else {
if (tianji[tianjiSlow] < king[kingFast])
result -= 200;
tianjiSlow++;
kingFast--;
}
}
}
return result;
}
2.3 事件序列问题（活动安排问题）
问题描述：有N个事件，每个事件有开始时间和结束时间。求最多能参加多少个不冲突的事件。
贪心策略：按结束时间从小到大排序，每次选择结束时间最早且不与已选事件冲突的事件。
struct Event {
int start;
int end;
};
bool cmp(Event a, Event b) {
return a.end < b.end; // 按结束时间升序排列
}
int maxEvents(Event events[], int n) {
sort(events, events + n, cmp);
int count = 1;
int lastEnd = events[0].end;
for (int i = 1; i < n; i++) {
if (events[i].start >= lastEnd) {
count++;
lastEnd = events[i].end;
}
}
return count;
}
正确性证明（反证法）： 假设存在最优解不包含最早结束的事件E，我们可以用E替换最优解中的第一个事件，得到的新解同样是最优解且包含E。
2.4 搬桌子问题
问题描述：走廊两侧各有200个房间，搬桌子需要占用走廊空间。两个任务若占用同一段走廊则必须分两趟完成。求完成所有任务的最少时间。
贪心策略：计算每段走廊被占用的次数，最大占用次数即为所需最少趟数。
int minTime(int tasks[][2], int n) {
int corridor[201] = {0}; // 走廊分段计数
for (int i = 0; i < n; i++) {
int start = (tasks[i][0] + 1) / 2; // 房间号映射到走廊下标
int end = (tasks[i][1] + 1) / 2;
if (start > end) swap(start, end);
for (int j = start; j <= end; j++) {
corridor[j]++;
}
}
int maxCount = 0;
for (int i = 1; i <= 200; i++) {
maxCount = max(maxCount, corridor[i]);
}
return maxCount * 10; // 每趟10分钟
}
2.5 删数问题
问题描述：给定一个长度不超过240位的正整数，删除其中S个数字后，剩下的数字按原次序组成新数。求最小的新数。
贪心策略：从左到右扫描，如果当前数字比后一个数字大，则删除当前数字。
string deleteDigits(string num, int s) {
string result;
int n = num.length();
for (int i = 0; i < n; i++) {
while (!result.empty() && result.back() > num[i] && s > 0) {
result.pop_back();
s--;
}
result.push_back(num[i]);
}
// 如果还有剩余删除次数，从末尾删除
while (s > 0 && !result.empty()) {
result.pop_back();
s--;
}
// 删除前导零
int start = 0;
while (start < result.length() && result[start] == '0') {
start++;
}
return start == result.length() ? "0" : result.substr(start);
}
3. 可图性判定问题
问题描述：给定一个非负整数序列，判断是否存在一个无向图，使得每个顶点的度数等于序列中对应的数。
贪心策略：Havel-Hakimi算法
- 将序列按非递增顺序排序
- 取出最大的数d，然后将后续d个数各减1
- 重复直到所有数都为0（可图）或出现负数（不可图）
bool isGraphic(vector<int> degrees) {
while (true) {
// 排序（降序）
sort(degrees.begin(), degrees.end(), greater<int>());
// 如果所有度都为0，则可图
if (degrees[0] == 0) return true;
// 取出最大的度
int d = degrees[0];
degrees.erase(degrees.begin());
// 如果d大于剩余顶点数，不可图
if (d > degrees.size()) return false;
// 将后续d个顶点的度减1
for (int i = 0; i < d; i++) {
degrees[i]--;
if (degrees[i] < 0) return false;
}
}
}
4. sort函数深度解析
4.1 基本用法
#include <algorithm>
using namespace std;
// 1. 基本类型排序
int arr[100];
sort(arr, arr + 100); // 默认升序
sort(arr, arr + 100, greater<int>()); // 降序
// 2. 自定义比较函数
bool cmp(int a, int b) {
return a > b; // 降序
}
sort(arr, arr + 100, cmp);
4.2 结构体排序
struct Student {
string name;
int score;
double height;
};
// 按分数降序，分数相同按身高升序
bool cmp(Student a, Student b) {
if (a.score != b.score)
return a.score > b.score;
return a.height < b.height;
}
Student students[100];
sort(students, students + 100, cmp);
4.3 字符串排序
#include <cstring>
struct Person {
char name[20];
int age;
};
bool cmp(Person a, Person b) {
// 按姓名字典序，姓名相同按年龄降序
if (strcmp(a.name, b.name) != 0)
return strcmp(a.name, b.name) < 0;
return a.age > b.age;
}
4.4 浮点数比较注意事项
// 错误的浮点数比较
if (a == b) // 可能因精度问题出错
// 正确的浮点数比较
bool equal(double a, double b) {
return fabs(a - b) < 1e-6;
}
bool cmp(double a, double b) {
if (fabs(a - b) < 1e-6) return false; // 认为相等
return a < b;
}
4.5 常见错误
// 错误：数据从下标1开始存储时
int arr[101];
// 初始化arr[1]到arr[100]
sort(arr, arr + 101); // 错误！包含了arr[0]
// 正确做法
sort(arr + 1, arr + 101); // 对arr[1]到arr[100]排序
5. 贪心算法应用技巧
5.1 贪心选择性质证明
贪心算法的正确性通常需要证明两个性质：
- 贪心选择性质：每一步的局部最优选择能导致全局最优解
- 最优子结构：问题的最优解包含子问题的最优解
5.2 常见贪心策略
- 排序贪心：先排序再选择（如事件序列问题）
- 区间贪心：处理区间问题（如搬桌子问题）
- 优先队列贪心：动态选择当前最优（如Huffman编码）
- 比例贪心：按性价比选择（如背包问题）
5.3 贪心与动态规划的区别
| 特征 | 贪心算法 | 动态规划 |
|---|---|---|
| 选择性质 | 局部最优选择 | 考虑所有可能选择 |
| 状态 | 无后效性 | 有重叠子问题 |
| 时间复杂度 | 通常较低 | 通常较高 |
| 适用范围 | 最优子结构+贪心选择性质 | 最优子结构+重叠子问题 |
6. 实战建议
- 多练习经典问题：熟练掌握常见贪心问题的解法
- 注意边界条件：特别是排序时的下标问题
- 验证贪心策略：用反例验证贪心策略的正确性
- 掌握sort函数：熟练使用各种排序规则
- 培养贪心思维：学会识别问题中的贪心性质
贪心算法虽然简单，但在很多实际问题中非常有效。通过系统学习和大量练习，你能够快速识别适用贪心算法的问题，并写出高效的解决方案。