贪心算法通过每步选择当前最优解以期望达到全局最优，适用于具有贪心选择性质和最优子结构的问题。
贪心算法是一种在每一步选择中都采取当前状态下最优的选择，希望最终结果是全局最优的策略。它不回溯，也不考虑未来的影响，只关注眼前最优。C++中实现贪心算法的关键在于明确问题是否适合贪心策略，并设计合理的贪心规则。
贪心算法的基本思路
贪心算法通常适用于具有“贪心选择性质”和“最优子结构”的问题。也就是说，局部最优解能导致全局最优解。常见应用场景包括：活动选择、区间调度、最小生成树（Prim、Kruskal）、霍夫曼编码、找零钱等。
实现步骤：
- 将问题分解为子问题
- 定义贪心策略（如按结束时间排序）
- 依次处理每个子问题，做出当前最优选择
- 合并结果
以活动选择问题为例
假设有n个活动，每个活动有开始时间和结束时间，目标是选出最多互不冲突的活动。
立即学习“C++免费学习笔记（深入）”；
贪心策略： 按照活动的结束时间升序排列，优先选择最早结束的活动。
#include#include #include using namespace std; struct Activity { int start, end; }; // 比较函数：按结束时间排序 bool compare(Activity a, Activity b) { return a.end < b.end; } void selectActivities(vector & activities) { // 按结束时间排序 sort(activities.begin(), activities.end(), compare); cout << "Selected activities:\n"; int i = 0; cout << "[" << activities[i].start << ", " << activities[i].end << "]\n"; // 遍历其余活动，选择与上一个不冲突的 for (int j = 1; j < activities.size(); j++) { if (activities[j].start >= activities[i].end) { cout << "[" << activities[j].start << ", " << activities[j].end << "]\n"; i = j; } } } int main() { vector acts = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}}; selectActivities(acts); return 0; }
输出结果会是最早结束且不重叠的活动序列，比如 [1,4], [5,7], [8,9]。
贪心算法的注意事项
并不是所有问题都能用贪心解决。使用前需验证贪心策略是否正确。例如，背包问题中，0-1背包不能用贪心，但分数背包可以（按单位价值排序）。
关键点：
- 排序往往是贪心的前提（如按结束时间、权重、密度等）
- 每一步的选择必须是不可逆的
- 需要数学证明或反例验证策略的正确性
