贪心算法（Greedy Algorithm）核心思想

每一步都做出当前最优选择，期望通过局部最优解叠加得到全局最优解。贪心算法不回溯，高效但不一定能得到全局最优解，需问题满足以下性质：

1. 贪心选择性质：局部最优能导向全局最优
2. 最优子结构：问题的最优解包含子问题的最优解

---

经典问题及C++实现

1. 活动选择问题（区间调度）

问题：选择最多数量的互不重叠活动
给定一组活动，每个活动都有一个开始时间和结束时间。选择最大的相互兼容的活动集合（即没有时间重叠的活动）。
策略：每次选结束时间最早的活动

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, end;
};

void selectActivities(vector<Activity> acts) {
    sort(acts.begin(), acts.end(), 
        [](const Activity& a, const Activity& b) {
            return a.end < b.end;  // 按结束时间升序
        });
    
    vector<Activity> selected = {acts[0]};
    int last_end = acts[0].end;
    
    for (int i = 1; i < acts.size(); ++i) {
        if (acts[i].start >= last_end) {
            selected.push_back(acts[i]);
            last_end = acts[i].end;
        }
    }
    
    // 输出结果
    cout << "Selected Activities:\n";
    for (auto& act : selected) 
        cout << "[" << act.start << ", " << act.end << "]\n";
}

int main() {
    vector<Activity> activities = {{1,3}, {2,5}, {3,7}, {5,9}, {8,10}};
    selectActivities(activities);
    return 0;
}

输出：

Selected Activities:
[1, 3]
[3, 7]
[8, 10]

---

2. 找零钱问题（硬币最小化）

问题：用最少的硬币凑出金额（假设硬币无限供应）
给定一些面额的硬币（无限供应）
和一个金额，找出用最少数量的硬币来凑成
这个金额。假设硬币面额是1元、2元、5
元、10元等（通常硬币面额是倍数关系时贪心
有效，否则可能要用动态规划）。
策略：优先使用大面额硬币

#include <iostream>
#include <vector>
using namespace std;

vector<int> coinChange(int amount, vector<int> coins) {
    sort(coins.rbegin(), coins.rend()); // 降序排序
    vector<int> result;
    
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            result.push_back(coin);
        }
    }
    return result;
}

int main() {
    vector<int> coins = {1, 2, 5, 10, 20, 50}; // 硬币面额
    int amount = 93;
    
    vector<int> change = coinChange(amount, coins);
    
    cout << "Coins for " << amount << ": ";
    for (int coin : change) cout << coin << " ";
    return 0;
}

输出：

Coins for 93: 50 20 20 2 1

---

3. 背包问题（分数版）

问题：物品可分割，最大化背包价值
策略：优先选择单位价值最高的物品

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    double weight, value;
};

double fractionalKnapsack(int capacity, vector<Item> items) {
    sort(items.begin(), items.end(), 
        [](const Item& a, const Item& b) {
            return a.value/a.weight > b.value/b.weight; // 按单位价值降序
        });
    
    double totalValue = 0.0;
    
    for (const Item& item : items) {
        if (capacity <= 0) break;
        double taken = min(item.weight, (double)capacity);
        totalValue += taken * (item.value / item.weight);
        capacity -= taken;
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
    int capacity = 50;
    
    cout << "Max value: " << fractionalKnapsack(capacity, items);
    return 0;
}

输出：

Max value: 240

---

贪心算法适用场景

问题类型	经典案例
区间调度	活动选择、会议室安排
哈夫曼编码	数据压缩
最小生成树	Prim/Kruskal算法
最短路径	Dijkstra算法
分数背包	物品可分割的背包问题

---

贪心 vs 动态规划

特性	贪心算法	动态规划
最优解	不一定全局最优	保证全局最优
复杂度	通常 O(n log n)	通常 O(n²) 或更高
回溯	无回溯	需保存子问题解
适用问题	满足贪心选择性质的问题	有重叠子问题的问题

⚠️ 贪心陷阱：不是所有问题都适用贪心（如0-1背包问题用贪心可能得不到最优解）

学习贪心算法的关键在于识别问题是否具有贪心性质，并通过练习加深理解。