L5_08 贪心算法

一、贪心算法概述

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

1.1 贪心算法的核心思想

贪心算法不从整体最优考虑，而是只关注当前步骤的最优选择。虽然这种策略不一定能保证得到全局最优解，但在许多问题中确实能得到最优解。

1.2 贪心算法的特点

• 优点：

  • 简单直观，易于实现
  • 时间复杂度较低
  • 通常不需要复杂的数据结构

• 缺点：

  • 不一定能得到全局最优解
  • 需要证明贪心选择的正确性

---

二、贪心算法的基本要素

2.1 最优子结构

问题的最优解包含其子问题的最优解。

2.2 贪心选择性质

在每一步选择中，选择当前最优的选项，可以得到全局最优解。

---

三、贪心算法的经典示例

3.1 活动选择问题

问题描述：给定一组活动及其开始和结束时间，选择最多的互不重叠的活动。

贪心策略：每次选择结束时间最早的活动。

struct Activity {
    int start;
    int end;
};

bool compareActivity(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

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

3.2 硬币找零问题

问题描述：给定不同面额的硬币，用最少的硬币数凑成给定金额。

贪心策略：每次选择面额最大的硬币。

int coinChangeGreedy(vector<int>& coins, int amount) {
    sort(coins.rbegin(), coins.rend());  // 按面额降序排序
    
    int count = 0;
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            count++;
        }
        if (amount == 0) break;
    }
    
    return amount == 0 ? count : -1;
}

注意：贪心算法并不适用于所有硬币系统，例如硬币面额为 {1, 3, 4}，金额为 6 时：

• 贪心：4 + 1 + 1 = 3 枚
• 最优：3 + 3 = 2 枚

3.3 区间覆盖问题

问题描述：给定一个区间 [start, end] 和一组子区间，选择最少的子区间覆盖整个区间。

贪心策略：每次选择覆盖当前位置且右端点最远的区间。

int intervalCover(vector<pair<int, int>>& intervals, int start, int end) {
    sort(intervals.begin(), intervals.end());
    
    int count = 0;
    int currentEnd = start;
    int i = 0;
    int n = intervals.size();
    
    while (currentEnd < end) {
        int farthest = currentEnd;
        
        while (i < n && intervals[i].first <= currentEnd) {
            farthest = max(farthest, intervals[i].second);
            i++;
        }
        
        if (farthest == currentEnd) {
            return -1;  // 无法覆盖
        }
        
        count++;
        currentEnd = farthest;
    }
    
    return count;
}

---

四、贪心算法在图论中的应用

4.1 哈夫曼编码

问题描述：给定字符出现的频率，构造最优前缀编码。

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
    
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

void printCodes(HuffmanNode* root, string code) {
    if (root == nullptr) return;
    
    if (root->ch != '\0') {
        cout << root->ch << ": " << code << endl;
        return;
    }
    
    printCodes(root->left, code + "0");
    printCodes(root->right, code + "1");
}

void huffmanEncoding(map<char, int>& freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    
    for (auto& pair : freq) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }
    
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        
        HuffmanNode* merged = new HuffmanNode('\0', left->freq + right->freq);
        merged->left = left;
        merged->right = right;
        
        pq.push(merged);
    }
    
    printCodes(pq.top(), "");
}

4.2 Prim 算法（最小生成树）

问题描述：在加权无向图中找到权值最小的生成树。

int primMST(vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    pq.push({0, 0});
    int totalWeight = 0;
    
    while (!pq.empty()) {
        auto [weight, u] = pq.top();
        pq.pop();
        
        if (visited[u]) continue;
        
        visited[u] = true;
        totalWeight += weight;
        
        for (auto [v, w] : graph[u]) {
            if (!visited[v]) {
                pq.push({w, v});
            }
        }
    }
    
    return totalWeight;
}

4.3 Kruskal 算法（最小生成树）

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

vector<int> parent;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[y] = x;
    }
}

int kruskalMST(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());
    
    parent.resize(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
    
    int totalWeight = 0;
    int edgeCount = 0;
    
    for (Edge& e : edges) {
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            totalWeight += e.weight;
            edgeCount++;
            
            if (edgeCount == n - 1) {
                break;
            }
        }
    }
    
    return totalWeight;
}

---

五、贪心算法的证明方法

5.1 交换论证

证明通过交换任意两个选择的顺序，不会使解变优。

5.2 归纳法

证明对于规模为 k 的问题，贪心选择可以得到最优解，然后证明对于规模为 k+1 的问题也成立。

---

六、贪心算法与动态规划的比较

特性	贪心算法	动态规划
选择方式	每步选择当前最优	考虑所有可能选择
最优子结构	必须满足	必须满足
重叠子问题	不要求	必须满足
时间复杂度	通常较低	通常较高
适用范围	较窄	较广

---

七、总结

贪心算法是一种简单而强大的算法设计策略，通过每一步的最优选择来追求全局最优。虽然它不能保证在所有问题中都得到最优解，但在许多实际问题中非常有效。掌握贪心算法需要理解其适用条件，并学会证明贪心选择的正确性。