贪心 [C++]

一、贪心算法的核心思想

局部最优 → 全局最优
在每一步选择中，仅考虑当前状态下最优的决策，不回溯或考虑未来步骤的影响。
无后效性
一旦做出选择，不会再改变（不可逆）。
适用条件
- 贪心选择性质：通过局部最优能推导全局最优。
- 最优子结构：问题的最优解包含子问题的最优解。

二、贪心算法的实现步骤

分解问题
将问题分解为多个子问题。
定义贪心策略
确定每一步选择的最优标准。
证明策略的有效性
确保局部最优能推导全局最优（通常通过数学归纳法）。
迭代求解
逐步构建问题的解。

三、经典贪心算法问题

1. 找零钱问题

问题描述：用最少的硬币数凑出指定金额（假设硬币面额是标准倍数关系，如1,5,10,25）。

C++实现：

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

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

int main() {
    vector<int> coins = {25, 10, 5, 1}; // 硬币面额
    int amount = 63;
    vector<int> res = greedyCoinChange(amount, coins);
    for (int c : res) cout << c << " "; // 输出：25 25 10 1 1 1 
    return 0;
}

2. 活动选择问题

问题描述：选择最多的互不重叠活动（按结束时间排序后，每次选最早结束的活动）。

C++实现：

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

struct Activity {
    int start, end;
};

int selectActivities(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), 
        [](const Activity& a, const Activity& b) { return a.end < b.end; });
    
    int count = 1, lastEnd = activities[0].end;
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= lastEnd) {
            count++;
            lastEnd = activities[i].end;
        }
    }
    return count;
}

四、贪心算法的应用场景

霍夫曼编码：构造最优前缀码。
最小生成树：Prim算法和Kruskal算法。
最短路径：Dijkstra算法（无负权边时）。
任务调度：如作业调度、CPU任务调度。

五、贪心算法的优缺点

优点	缺点
实现简单，运行高效（通常O(n)或O(n log n))	不保证全局最优（需严格证明适用性）
适用于实时系统或大规模数据	对问题条件要求严格

六、贪心 vs 动态规划

贪心算法	动态规划
无后效性，仅依赖当前状态	依赖子问题的历史状态
效率更高	可能更通用，但复杂度更高
需要严格证明	通过递推公式保证正确性

七、如何验证贪心策略？

数学归纳法：证明每一步的贪心选择能导向全局最优。
反证法：假设存在更优解，推导矛盾。
替换法：将贪心解与假设的最优解对比。

总结

贪心算法的核心在于通过局部最优的快速决策逼近全局最优，适用于满足特定条件的问题。在C++实现时，通常需要结合排序和迭代操作，重点在于策略的合理性和正确性证明。实际应用中需仔细分析问题是否满足贪心算法的前提条件。