贪心算法，就像在迷宫中每次只选择当前看起来最短的那条路——它不保证全局最优，但常常能高效地找到不错的解决方案。

在算法世界里，贪心算法以其直观、高效的特点占据着重要地位。它不像动态规划那样需要考虑所有子问题，也不像回溯算法那样需要尝试所有可能。贪心算法的核心思想是：每一步都做出在当前看来最好的选择，希望通过局部最优的选择达到全局最优。

本文将带你深入理解贪心算法，并通过C++代码实例展示如何应用这一强大的算法思想。

什么是贪心算法？

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法策略。

核心特点：

局部最优选择： 每一步都选择当前最优的选项
不可撤销： 一旦做出选择，就不回头重新考虑
高效简单： 通常时间复杂度较低，实现相对简单
贪心算法适用于贪心选择性质和最优子结构的问题：
贪心选择性质： 通过局部最优选择能达到全局最优
最优子结构： 问题的最优解包含子问题的最优解

经典贪心问题与C++实现

问题1：活动选择问题
问题描述：有n个活动，每个活动有开始时间和结束时间。选择尽可能多的互不冲突的活动。

贪心策略：每次选择结束时间最早的活动，这样能为后续活动留出更多时间。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Activity {
    int start;      // 开始时间
    int end;        // 结束时间
    int index;      // 原始索引（便于输出）
    
    Activity(int s, int e, int i) : start(s), end(e), index(i) {}
};

// 比较函数：按结束时间升序排序
bool compareActivities(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

void selectActivities(vector<Activity>& activities) {
    if (activities.empty()) return;
    
    // 步骤1：按结束时间排序
    sort(activities.begin(), activities.end(), compareActivities);
    
    cout << "选择的活动: ";
    
    // 步骤2：贪心选择
    int lastEnd = activities[0].end;
    cout << "活动" << activities[0].index + 1 << " ";
    
    for (int i = 1; i < activities.size(); i++) {
        // 如果当前活动的开始时间 >= 上一个活动的结束时间，则选择
        if (activities[i].start >= lastEnd) {
            cout << "活动" << activities[i].index + 1 << " ";
            lastEnd = activities[i].end;
        }
    }
    cout << endl;
}

int main() {
    vector<Activity> activities = {
        Activity(1, 4, 0),   // 活动1: 1-4
        Activity(3, 5, 1),   // 活动2: 3-5
        Activity(0, 6, 2),   // 活动3: 0-6
        Activity(5, 7, 3),   // 活动4: 5-7
        Activity(3, 9, 4),   // 活动5: 3-9
        Activity(5, 9, 5),   // 活动6: 5-9
        Activity(6, 10, 6),  // 活动7: 6-10
        Activity(8, 11, 7),  // 活动8: 8-11
        Activity(8, 12, 8),  // 活动9: 8-12
        Activity(2, 13, 9),  // 活动10: 2-13
        Activity(12, 14, 10) // 活动11: 12-14
    };
    
    selectActivities(activities);
    
    return 0;
}

问题2：分数背包问题
问题描述：给定n个物品和一个容量为W的背包。物品i有重量wi和价值vi。可以带走物品的一部分，求最大价值。

贪心策略：每次选择单位重量价值最高的物品（性价比最高）。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item {
    int weight;     // 重量
    int value;      // 价值
    double ratio;   // 单位重量价值（性价比）
    
    Item(int w, int v) : weight(w), value(v) {
        ratio = (double)v / w;
    }
};

// 比较函数：按性价比降序排序
bool compareItems(const Item& a, const Item& b) {
    return a.ratio > b.ratio;
}

double fractionalKnapsack(int capacity, vector<Item>& items) {
    // 按性价比降序排序
    sort(items.begin(), items.end(), compareItems);
    
    double totalValue = 0.0;
    int remainingCapacity = capacity;
    
    for (const Item& item : items) {
        if (remainingCapacity <= 0) break;
        
        if (item.weight <= remainingCapacity) {
            // 整个物品都能装下
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            // 只能装下一部分
            double fraction = (double)remainingCapacity / item.weight;
            totalValue += item.value * fraction;
            remainingCapacity = 0;
        }
    }
    
    return totalValue;
}

int main() {
    vector<Item> items = {
        Item(10, 60),   // 物品1: 重量10, 价值60
        Item(20, 100),  // 物品2: 重量20, 价值100
        Item(30, 120)   // 物品3: 重量30, 价值120
    };
    
    int capacity = 50;
    double maxValue = fractionalKnapsack(capacity, items);
    
    cout << "背包容量: " << capacity << endl;
    cout << "最大价值: " << maxValue << endl;
    
    // 输出详细信息
    cout << "物品详情:" << endl;
    for (int i = 0; i < items.size(); i++) {
        cout << "物品" << i + 1 
             << ": 重量=" << items[i].weight 
             << ", 价值=" << items[i].value
             << ", 性价比=" << items[i].ratio << endl;
    }
    
    return 0;
}

贪心算法的优缺点

优点：
高效简单：时间复杂度通常较低
易于实现：思路清晰，代码直观
空间效率高：通常不需要额外的数据结构
缺点：
可能得不到全局最优解：贪心选择不一定是全局最优
适用范围有限：只适用于具有贪心选择性质的问题
难以证明正确性：有时难以证明贪心策略的正确性