掌握C++贪心算法（从零开始的贪心策略实战指南）

什么是贪心算法？

贪心算法（Greedy Algorithm）的核心思想是：在每一步决策中，都做出在当前看来最好的选择，而不考虑未来的影响。这种“短视”策略在某些特定问题上却能神奇地得到全局最优解。

常见的适用贪心算法的问题包括：

• 活动选择问题
• 找零钱问题（特定币值系统）
• 最小生成树（Kruskal、Prim算法）
• 霍夫曼编码

贪心算法的两个关键性质

1. 贪心选择性质：可以通过局部最优选择来构造全局最优解。
2. 最优子结构：一个问题的最优解包含其子问题的最优解。

实战案例：活动选择问题

假设你有一系列活动，每个活动有开始时间和结束时间。你的目标是选择尽可能多的互不冲突的活动。这就是经典的活动选择问题，非常适合用贪心策略C++来解决。

贪心策略：总是优先选择结束时间最早的活动，这样可以为后续活动留下最多的时间。

C++代码实现

#include <iostream>#include <vector>#include <algorithm>using namespace std;// 定义活动结构体struct Activity {    int start;    int end;};// 按结束时间升序排序bool compare(Activity a, Activity b) {    return a.end < b.end;}// 贪心算法选择最大兼容活动集vector<Activity> selectActivities(vector<Activity>& activities) {    // 第一步：按结束时间排序    sort(activities.begin(), activities.end(), compare);        vector<Activity> result;    result.push_back(activities[0]); // 选择第一个活动（结束最早）        int lastEnd = activities[0].end;        // 遍历其余活动    for (int i = 1; i < activities.size(); i++) {        if (activities[i].start >= lastEnd) {            result.push_back(activities[i]);            lastEnd = activities[i].end;        }    }        return result;}int main() {    vector<Activity> acts = {{1, 3}, {2, 5}, {4, 7}, {6, 9}, {8, 10}};        vector<Activity> selected = selectActivities(acts);        cout << "选中的活动数量: " << selected.size() << endl;    for (auto& act : selected) {        cout << "[" << act.start << ", " << act.end << "] ";    }    cout << endl;        return 0;}

这段代码展示了如何使用C++算法入门级别的贪心策略解决活动选择问题。程序首先将活动按结束时间排序，然后依次选择不与已选活动冲突的最早结束活动。

贪心算法的局限性

需要注意的是，并非所有问题都能用贪心算法求得最优解。例如，在一般的找零钱问题中（如币值为{1, 3, 4}，要凑出6元），贪心策略（先选4，再选1+1）得到3枚硬币，而最优解是3+3只需2枚。

因此，在使用贪心算法教程中强调的方法前，务必验证问题是否满足贪心选择性质和最优子结构。

总结

贪心算法是一种强大而简洁的算法设计技巧。通过本篇C++贪心算法教程，你应该已经掌握了：

• 贪心算法的基本思想
• 适用贪心策略的问题特征
• 如何用C++实现一个典型的贪心算法
• 贪心算法的局限性

继续练习更多贪心问题（如分数背包、区间覆盖等），你将更深入理解这一经典策略。祝你在C++算法入门之路上越走越远！