一文读懂贪心算法：原理、实战案例与代码实现在算法世界中，贪心算法是一种直观且高效的解题思路，它凭借 “局部最优” 推导 “全局最优” 的特性，在众多场景中展现出简洁实用的优势。本文将从贪心算法的核心原理入手，结合实际应用案例与代码实现，带你快速掌握这一经典算法。
一、贪心算法是什么？核心原理拆解1. 定义：“只顾眼前最优” 的解题思路贪心算法（Greedy Algorithm）是一种启发式算法，它在解决问题时，每一步都做出当前状态下 “最优” 的选择（即局部最优解），并期望通过这些局部最优解的累积，最终得到全局最优解。
简单来说，贪心算法不考虑未来可能的情况，也不回溯调整之前的选择，始终沿着 “当前最好” 的路径前进。例如生活中 “找零尽量用大面额硬币”“挑选会议时优先选结束早的场次”，本质都是贪心思想的体现。
2. 关键特性：适用贪心算法的 2 个前提并非所有问题都能用贪心算法解决，它的有效性依赖两个核心前提：
贪心选择性质：每一步的局部最优选择，能够导向全局最优解。例如 “找零问题” 中，每次选最大面额硬币，最终能得到硬币数量最少的方案（前提是硬币面额满足 “贪心兼容性”，如人民币、美元面额）。
最优子结构：问题的全局最优解，包含其子问题的最优解。例如 “最短路径问题” 中，从 A 到 C 的最短路径，若经过 B，则 A 到 B、B 到 C 的路径也必须是各自的最短路径。
3. 与其他算法的区别：贪心 vs 动态规划很多人会混淆贪心算法与动态规划，二者核心差异在于是否回溯：
贪心算法：不回溯，一旦做出选择就不再调整，时间复杂度更低（通常为 O (n log n)），但仅适用于满足 “贪心性质” 的问题。动态规划：会记录子问题的所有解，通过回溯或递推选择最优解，适用于更复杂的问题（如背包问题），但时间 / 空间复杂度更高。二、贪心算法经典应用案例与代码实现下面通过 3 个高频应用场景，带你实战贪心算法的解题思路，所有代码均基于 C++ 实现，兼顾可读性与效率。
案例 1：找零问题（基础入门）问题描述假设货币面额为 [1, 5, 10, 20, 50, 100]（单位：元），给定需要找零的金额 amount，求最少需要多少枚硬币。
贪心思路利用 “每次选最大面额硬币” 的策略：
从最大面额（100 元）开始，尽可能多地使用该面额硬币；剩余金额用次大面额（50 元）继续填充，依次类推；直到剩余金额为 0，统计总硬币数。代码实现
#include
#include
#include // 用于sort（若面额未排序）
using namespace std;
// 找零函数：返回最少硬币数，coins为排序后的面额（从大到小）
int minCoins(int amount, vector& coins) {
// 确保面额从大到小排序（若输入未排序）
sort(coins.rbegin(), coins.rend());
int coinCount = 0; // 总硬币数
int remaining = amount; // 剩余待找零金额
for (int coin : coins) {
if (remaining <= 0) break; // 金额已找完，退出循环
// 计算当前面额最多能使用的硬币数
int count = remaining / coin;
coinCount += count;
remaining -= count * coin; // 更新剩余金额
// 打印每一步选择（可选，用于调试）
cout << "使用" << count << "枚" << coin << "元硬币，剩余金额：" << remaining << "元" << endl;
}
// 若剩余金额不为0，说明无法用现有面额找零（本题面额包含1元，不会出现此情况）
return remaining == 0 ? coinCount : -1;
}
int main() {
vector coins = {1, 5, 10, 20, 50, 100}; // 货币面额
int amount = 268; // 需要找零的金额
int result = minCoins(amount, coins);
cout << "找零" << amount << "元最少需要" << result << "枚硬币" << endl;
return 0;
}
输出结果
使用2枚100元硬币，剩余金额：68元
使用1枚50元硬币，剩余金额：18元
使用0枚20元硬币，剩余金额：18元
使用1枚10元硬币，剩余金额：8元
使用1枚5元硬币，剩余金额：3元
使用3枚1元硬币，剩余金额：0元
找零268元最少需要8枚硬币
案例 2：活动选择问题（区间调度经典）问题描述有 n 个活动，每个活动有开始时间 start[i] 和结束时间 end[i]，同一时间只能进行一个活动，求最多能选择多少个互不冲突的活动。
贪心思路核心策略：优先选择结束时间最早的活动，这样能为后续活动留出更多时间，从而最大化活动数量：
将所有活动按结束时间从小到大排序；选择第一个活动（结束时间最早），并记录其结束时间；依次遍历后续活动，若活动的开始时间 ≥ 上一个活动的结束时间，则选择该活动，更新结束时间；遍历结束后，统计选择的活动总数。代码实现
#include
#include
#include
using namespace std;
// 定义活动结构体：包含开始时间和结束时间
struct Activity {
int start;
int end;
};
// 排序规则：按结束时间从小到大排序
bool compareActivity(const Activity& a, const Activity& b) {
return a.end < b.end;
}
// 选择最多不冲突活动的函数
vector selectMaxActivities(vector& activities) {
vector selected; // 存储选择的活动
if (activities.empty()) return selected;
// 1. 按结束时间排序
sort(activities.begin(), activities.end(), compareActivity);
// 2. 选择第一个活动（结束时间最早）
selected.push_back(activities[0]);
int lastEnd = activities[0].end; // 记录上一个活动的结束时间
// 3. 遍历后续活动，选择不冲突的
for (int i = 1; i < activities.size(); ++i) {
if (activities[i].start >= lastEnd) { // 活动开始时间不早于上一个结束时间
selected.push_back(activities[i]);
lastEnd = activities[i].end; // 更新结束时间
}
}
return selected;
}
int main() {
// 示例活动：(start, end)
vector activities = {
{1, 4}, {3, 5}, {0, 6}, {5, 7},
{3, 8}, {5, 9}, {6, 10}, {8, 11}
};
vector result = selectMaxActivities(activities);
// 输出结果
cout << "最多能选择" << result.size() << "个不冲突的活动，分别是：" << endl;
for (const auto& act : result) {
cout << "活动：开始时间" << act.start << "，结束时间" << act.end << endl;
}
return 0;
}
输出结果
最多能选择4个不冲突的活动，分别是：
活动：开始时间1，结束时间4
活动：开始时间5，结束时间7
活动：开始时间8，结束时间11
案例 3：分糖果问题（贪心策略进阶）问题描述有 n 个孩子，每个孩子有一个评分 ratings[i]，现在要给孩子分糖果，规则是：
每个孩子至少分到 1 颗糖果；评分更高的孩子，得到的糖果数必须比相邻（左边或右边）评分低的孩子多。求最少需要多少颗糖果。
贪心思路该问题需要 “双向贪心”，因为每个孩子的糖果数受左右两个邻居影响：
从左到右遍历：确保每个孩子的糖果数 ≥ 左边评分低的孩子（若当前评分 > 左边，则糖果数 = 左边 + 1）；从右到左遍历：确保每个孩子的糖果数 ≥ 右边评分低的孩子（若当前评分 > 右边，则糖果数 = max (当前糖果数，右边 + 1)）；遍历结束后，累加所有孩子的糖果数，即为最少总糖果数。代码实现
#include
#include
#include // 用于max函数
using namespace std;
int minCandies(vector& ratings) {
int n = ratings.size();
if (n == 0) return 0;
vector candies(n, 1); // 初始化：每个孩子至少1颗糖果
// 1. 从左到右：确保右边评分高的孩子糖果数 > 左边
for (int i = 1; i < n; ++i) {
if (ratings[i] > ratings[i-1]) {
candies[i] = candies[i-1] + 1;
}
}
// 2. 从右到左：确保左边评分高的孩子糖果数 > 右边
for (int i = n-2; i >= 0; --i) {
if (ratings[i] > ratings[i+1]) {
candies[i] = max(candies[i], candies[i+1] + 1);
}
}
// 3. 计算总糖果数
int total = 0;
for (int c : candies) {
total += c;
}
return total;
}
int main() {
vector ratings = {1, 2, 2}; // 孩子评分示例
int result = minCandies(ratings);
cout << "最少需要" << result << "颗糖果" << endl;
return 0;
}
输出结果
最少需要4颗糖果
（解释：3 个孩子的糖果数分别为 1、2、1，总和为 4，满足所有规则）
三、贪心算法的局限性与使用建议1. 局限性：并非万能算法无法保证全局最优：若问题不满足 “贪心选择性质”，贪心算法可能得到局部最优而非全局最优。例如 “0-1 背包问题”（物品不可分割），用贪心算法选单价最高的物品，可能无法装满背包，导致总价值不是最大；而动态规划能得到全局最优。依赖问题结构：贪心策略的设计高度依赖问题本身的结构，例如 “找零问题” 若面额为 [1, 3, 4]，找零 6 元时，贪心选 4+1+1（3 枚），但最优解是 3+3（2 枚），此时贪心算法失效。2. 使用建议：3 步判断是否用贪心分析问题性质：判断是否满足 “贪心选择性质” 和 “最优子结构”（可通过反例验证，若存在反例则不适用）；设计贪心策略：明确每一步的 “局部最优” 标准（如 “结束最早”“面额最大”“价值最高”）；验证有效性：通过小案例测试策略是否能得到全局最优，或查阅是否有该问题的贪心算法证明。四、总结贪心算法是一种 “简单高效” 的解题思路，核心在于 “局部最优推导全局最优”，适用于找零、区间调度、资源分配等场景。它的优势是时间复杂度低、实现简洁，不足是依赖问题性质，并非所有问题都适用。
掌握贪心算法的关键，在于理解其适用前提，并能针对具体问题设计合理的贪心策略。通过本文的案例练习，相信你已能初步运用贪心算法解决实际问题，后续可结合动态规划、回溯算法等，形成更完整的算法思维体系。