#创作计划#贪心算法
2025-09-15 20:36:41
发布于：江苏
38阅读
0回复
0点赞
0.目录：
1.第一部分：导言 —— 为什么需要贪心算法？
2.第二部分：什么是贪心算法？
3.第三部分：贪心算法的完整使用方法
4.第四部分：贪心算法的常见问题与解决方案
5.第五部分：总结与拓展
第一部分：导言 —— 为什么需要贪心算法？
在算法设计中，我们常面临两类核心需求：追求最优解（如最少硬币数、最多活动数）和追求高效解（如降低时间复杂度）。传统暴力枚举法虽能遍历所有可能，但面对大规模数据时（如 1e5 级别的元素），会因时间复杂度过高（如O（ ）、O（n！））直接超时，无法实用。
·生活中 “找零优先用大面额硬币”“选课优先选早结束的课程”，本质都是贪心策略的应用；
·算法竞赛中 “区间覆盖”“哈夫曼编码” 等经典问题，贪心算法是最优解决方案。
第二部分：什么是贪心算法？
贪心算法的本质是 “短视的最优决策”—— 它不考虑未来步骤的影响，仅在当前状态下选择 “看起来最好” 的选项，通过逐步累积局部最优解，最终期望得到全局最优解。
2.1 贪心算法的底层逻辑
贪心算法的执行依赖 “两步走” 逻辑，缺一不可：
1.局部最优选择：每一步都选择当前状态下最优的选项（如 “最大面额硬币”“最早结束活动”），且该选择一旦做出便不可逆；
2.问题规模缩减：每完成一次局部选择后，原问题会转化为一个更小的子问题（如找零金额减少、剩余活动范围缩小），重复步骤 1 直到子问题解决。
2.2 贪心 vs 暴力枚举：核心优势对比
| 特性 | 暴力枚举 | 贪心算法 |
|---|---|---|
| 决策逻辑 | 枚举所有活动组合，筛选不冲突的最大集合 | 每步选最早结束的活动，逐步筛选 |
| 时间复杂度 | O（）（n=10 时为 1024 次计算） | O (nlogn)（排序占主导，n=10 时仅需 30 次左右计算） |
| 空间复杂度 | O (n)（存储所有组合） | O (1)（仅存储当前选择状态） |
| 实用性 | 仅适用于 n≤20 的小规模问题 | 支持 n=1e5 的大规模问题 |
第三部分：贪心算法的完整使用方法
3.1 前置准备：明确贪心算法的适用条件
并非所有问题都能使用贪心算法，必须满足以下两个核心性质，否则局部最优的累积会导致全局次优：
性质 1：贪心选择性质
每一步的局部最优选择，必然能导向全局最优解
可通过 “反证法” 验证：假设某一步不选局部最优选项，而选择其他选项，最终得到的全局解会比选局部最优时更差。
例如 “活动选择问题”：若某一步不选最早结束的活动 A，而选结束更晚的活动 B，那么 B 会占用更多后续时间，导致能选择的总活动数减少，全局解更差。
性质 2：最优子结构
全局最优解包含其子问题的最优解。
即问题的最优解可以拆分为多个子问题的最优解，且子问题的最优解可独立求解。
例如 “钱币找零问题”（适合贪心的面额体系）：凑出金额 186 元的最优解（100+50+20+10+5+1），包含凑出 86 元的最优解（50+20+10+5+1），而 86 元的最优解又包含 36 元的最优解（20+10+5+1），以此类推。
3.2 贪心算法的 4 步核心流程
使用贪心算法解决任何问题，都可遵循固定流程，核心是 “确定贪心策略”：
1.问题拆解：将原问题拆分为多个连续的子问题（如 “凑 186 元” 拆分为 “先选最大面额，再凑剩余金额”）；
2.定义贪心策略：明确 “什么是当前子问题的局部最优选择”（如 “优先选最大面额硬币”“优先选最早结束活动”）；
3.执行局部选择：按策略做出当前选择，更新问题状态（如减少待凑金额、更新已覆盖时间范围），缩小问题规模；
4.验证全局最优：（可选）通过数学归纳法或反证法证明，所有局部最优选择的累积结果即为全局最优（竞赛中若问题经典可省略）。
3.3 经典问题实战：2 类高频场景
场景 1：活动选择问题（最多参加活动数）
问题描述
给定 n 个活动，每个活动有开始时间 start[i] 和结束时间 end[i]，同一时间只能参加一个活动，求最多能参加的活动数量。
贪心策略
优先选择 “最早结束” 的活动—— 最早结束的活动能留下最多时间给后续活动，是局部最优选择。
AC代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义活动结构体：存储开始时间和结束时间
struct abc {
int a;
int b;
};
// 排序规则：按结束时间升序排列（贪心策略的核心）
bool cde(const abc& d, const abc& e) {
return d.b < e.b; // 结束时间早的活动排在前面
}
// 计算最多可参加的活动数
int aabbccdd(vector<abc>& f) {
// 边界处理：无活动时返回 0
if (f.empty()) return 0;
// 步骤 1：按贪心策略排序（结束时间升序）
sort(f.begin(), f.end(), cde);
// 步骤 2：执行局部选择，累积结果
int g = 1; // 至少能参加第一个活动
int h = f[0].b; // 记录上一个参加活动的结束时间
// 遍历后续活动，选择与上一个活动不冲突的（当前活动开始时间 ≥ 上一个结束时间）
for (int i = 1; i < f.size(); ++i) {
if (f[i].a >= h) {
g++; // 选择当前活动
h = f[i].b; // 更新结束时间
}
}
return g;
}
int main() {
// 测试数据：6 个活动
vector<abc> i = {
{1, 2}, {3, 4}, {0, 6},
{5, 7}, {8, 9}, {5, 9}
};
int j = aabbccdd(i);
cout << "最多可参加的活动数：" << j << endl;
// 输出：4（选择 {1,2}, {3,4}, {5,7}, {8,9}）
return 0;
}
关键细节解析
·排序的必要性：若不排序，无法快速找到 “最早结束的活动”，会导致局部选择错误；
场景 2：钱币找零问题（最少硬币数）
问题描述
给定一套硬币面额（如 1、5、10、20、50、100），以及一个目标金额，每种硬币数量无限，求凑出目标金额所需的最少硬币数（假设面额体系适合贪心）。
贪心策略
优先选择 “面额最大” 的硬币—— 大面额硬币能快速减少待凑金额，减少总硬币数，是局部最优选择。
AC代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 计算最少硬币数，若无法凑出返回 -1
int aabbccdd(vector<int>& a, int b) {
// 边界处理：金额为 0 时无需硬币
if (b == 0) return 0;
// 边界处理：无硬币或金额为负时无法凑出
if (a.empty() || b < 0) return -1;
// 步骤 1：按贪心策略排序（面额降序）
sort(a.rbegin(), a.rend()); // 反向排序，大面额在前
int c = 0; // 总硬币数
int d = b; // 剩余待凑金额
// 步骤 2：执行局部选择，优先用大面额硬币
for (int e : a) {
if (d >= e) {
int f = d / e; // 当前面额最多可用的数量
c += f; // 累加硬币数
d -= f * e; // 更新剩余金额
}
// 提前退出：金额已凑完
if (d == 0) break;
}
// 步骤 3：判断是否能完全凑出金额
return d == 0 ? c : -1;
}
int main() {
// 测试数据：人民币面额（适合贪心）
vector<int> g = {1, 5, 10, 20, 50, 100};
int h = 186;
int i = aabbccdd(g, h);
if (i != -1) {
cout << "最少硬币数：" << i << endl;
// 输出：6（100+50+20+10+5+1=186）
} else {
cout << "无法凑出目标金额" << endl;
}
return 0;
}
关键细节解析
·面额体系的限制：贪心仅适用于 “每一面额都能被更小面额组合覆盖” 的体系（如人民币、美元），若面额为 {1,3,4}，凑 6 元时贪心会选 4+1+1（3 枚），而最优解是 3+3（2 枚），此时需改用动态规划；
第四部分：贪心算法的常见问题与解决方案
4.1 问题 1：如何判断问题是否适合贪心？
解决方案：通过 “反证法”+“样例测试” 验证：
1.假设某一步不选局部最优选项，看是否能得到更优的全局解；
2.构造多个测试样例（尤其是边界情况，如金额为 0、区间无重叠），验证贪心结果是否与最优解一致。
4.2 问题 2：贪心策略不唯一时如何选择？
解决方案：根据问题目标确定策略方向：
·若目标是 “最大化数量”（如活动选择），通常优先选 “占用资源少” 的选项（如早结束、短时长）；
·若目标是 “最小化数量”（如找零、区间覆盖），通常优先选 “贡献资源多” 的选项（如大面额、广覆盖）。
4.3 问题 3：贪心结果不是最优时怎么办？
解决方案：改用其他算法，常见替代方案：
·动态规划：适用于不满足贪心选择性质，但存在最优子结构的问题（如 {1,3,4} 面额的找零问题）；
·回溯法：适用于小规模问题，需枚举所有可能解（如小规模的区间选择问题）。
第五部分：总结与拓展
5.1 贪心算法的核心优势与局限
| 优势 | 局限 |
|---|---|
| 时间复杂度低（多为 O (nlogn)），适合大规模数据 | 仅适用于满足 “贪心选择性质” 和 “最优子结构” 的问题 |
| 逻辑直观，代码实现简单 | 无法回溯，一步错则全局错（需严格验证策略） |
| 空间复杂度低（多为 O (1) 或 O (n)） | 部分问题需结合排序，排序效率影响整体性能 |
5.2 拓展学习：进阶贪心问题
·哈夫曼编码：通过贪心选择 “频率最低的两个节点” 构建最优前缀编码，用于数据压缩；
·任务调度问题：优先调度 “剩余次数最多” 的任务，最小化总调度时间；
· fractional 背包问题 ：优先选择 “单位价值最高” 的物品，最大化背包总价值（与 0-1 背包区分，0-1 背包需用动态规划）。
有帮助，赞一个