贪心算法在C++中的应用与实践

一、贪心算法基础

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优决策的算法策略。其核心特点是：

• 局部最优选择：不考虑长远影响

• 无后效性：当前决策不影响之前状态

• 高效性：通常时间复杂度较低

// 经典贪心问题：找零钱
vector<int> greedyChange(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 amount == 0 ? result : vector<int>();
}

二、典型问题解析

1. 区间调度问题

struct Interval {
    int start, end;
};

int intervalSchedule(vector<Interval>& intervals) {
    sort(intervals.begin(), intervals.end(), 
        [](auto& a, auto& b){ return a.end < b.end; });
    
    int count = 0, end = INT_MIN;
    for(auto& inv : intervals){
        if(inv.start >= end){
            count++;
            end = inv.end;
        }
    }
    return count;
}

2. 霍夫曼编码

struct Node {
    char ch;
    int freq;
    Node *left, *right;
};

struct comp {
    bool operator()(Node* l, Node* r){
        return l->freq > r->freq;
    }
};

Node* buildHuffmanTree(string text) {
    // 统计频率
    unordered_map<char, int> freq;
    for(char c : text) freq[c]++;
    
    // 优先队列
    priority_queue<Node*, vector<Node*>, comp> pq;
    for(auto& p : freq)
        pq.push(new Node{p.first, p.second, nullptr, nullptr});
    
    // 构建树
    while(pq.size() > 1){
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node{'\0', left->freq+right->freq, left, right};
        pq.push(parent);
    }
    return pq.top();
}

三、贪心算法的正确性证明

1. 贪心选择性质：证明局部最优能导致全局最优

2. 最优子结构：问题的最优解包含子问题的最优解

3. 常用证明方法：

   • 数学归纳法

   • 交换论证法

   • 决策树分析法

四、C++实现技巧

1. 优先队列的使用：

priority_queue<int, vector<int>, greater<int>> minHeap;

1. 自定义排序：

sort(items.begin(), items.end(), [](auto& a, auto& b){
    return a.value/(double)a.weight > b.value/(double)b.weight;
});

1. STL算法组合：

auto it = max_element(begin, end, comp);

五、贪心算法的局限性

1. 不适用于需要全局考虑的问题

2. 可能陷入局部最优而非全局最优

3. 典型反例：0-1背包问题

六、实战练习建议

1. LeetCode经典题目：

   • 分发饼干

   • 买卖股票的最佳时机II

   • 无重叠区间

2. 调试技巧：

#define DEBUG
#ifdef DEBUG
    #define debug(x) cout << #x << " = " << x << endl
#else
    #define debug(x)
#endif

七、进阶思考

1. 贪心算法与动态规划的关系

2. 拟阵理论与贪心算法

3. 近似算法中的贪心策略