贪心算法（Greedy Algorithm）

贪心算法（Greedy Algorithm）是一种在每一步选择中都接纳当前状态下最优决策的算法头脑。它通过局部最优的选择，希望终极达到全局最优解。贪心算法并不总是能得到全局最优解，但在某些问题上非常有效。

---

1. 贪心算法的核心头脑

• 局部最优：在每一步选择中，选择当前状态下最优的决策。
  
• 无后效性：当前的选择不会影响后续的选择。
  
• 贪心选择性质：通过局部最优选择，终极能够得到全局最优解。
  

---

2. 贪心算法的适用条件

贪心算法适用于满足以下条件的问题：

• 最优子结构：问题的最优解包含子问题的最优解。
  
• 贪心选择性质：通过局部最优选择，能够得到全局最优解。
  

---

3. 贪心算法的经典问题

1. 找零问题

• 问题描述：给定不同面额的硬币和一个总金额，求最少必要多少硬币。
  
• 贪心策略：每次选择面额最大的硬币。
  
• 代码实现：
  1. int coinChange(vector<int>& coins, int amount) {
  2.     sort(coins.rbegin(), coins.rend());  // 按面额从大到小排序
  3.     int count = 0;
  4.     for (int coin : coins) {
  5.         while (amount >= coin) {
  6.             amount -= coin;
  7.             count++;
  8.         }
  9.     }
  10.     return amount == 0 ? count : -1;  // 如果无法凑出金额，返回 -1
  11. }

  复制代码

2. 活动选择问题

• 问题描述：给定一组活动，每个活动有开始时间和竣事时间，求最多能安排多少个互不冲突的活动。
  
• 贪心策略：每次选择竣事时间最早的活动。
  
• 代码实现：
  1. int maxActivities(vector<pair<int, int>>& activities) {
  2.     sort(activities.begin(), activities.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
  3.         return a.second < b.second;  // 按结束时间排序
  4.     });
  5.     int count = 1;
  6.     int last_end = activities[0].second;
  7.     for (int i = 1; i < activities.size(); i++) {
  8.         if (activities[i].first >= last_end) {
  9.             count++;
  10.             last_end = activities[i].second;
  11.         }
  12.     }
  13.     return count;
  14. }

  复制代码

3. 背包问题（分数背包）

• 问题描述：给定一组物品，每个物品有重量和代价，背包有容量限制，求能装入的最大代价（物品可以分割）。
  
• 贪心策略：每次选择单位重量代价最高的物品。
  
• 代码实现：
  1. double fractionalKnapsack(int capacity, vector<pair<int, int>>& items) {
  2.     sort(items.begin(), items.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
  3.         return (double)a.second / a.first > (double)b.second / b.first;  // 按单位重量价值排序
  4.     });
  5.     double max_value = 0;
  6.     for (auto& item : items) {
  7.         if (capacity >= item.first) {
  8.             capacity -= item.first;
  9.             max_value += item.second;
  10.         } else {
  11.             max_value += (double)item.second / item.first * capacity;
  12.             break;
  13.         }
  14.     }
  15.     return max_value;
  16. }

  复制代码

---

4. 贪心算法的范围性

贪心算法并不总是能得到全局最优解。例如：

• 0-1 背包问题：物品不能分割，贪心算法无法得到最优解。
  
• 最短路径问题：Dijkstra 算法是贪心算法，但不适用于负权边。
  

---

5. 贪心算法的总结

• 优点：
  
  
  
  • 简单易实现。
    
  • 时间复杂度通常较低。
    
  
  
• 缺点：
  
  
  
  • 不适用于所有问题。
    
  • 无法保证全局最优解。
    
  
  
• 适用场景：
  
  
  
  • 问题具有最优子结构和贪心选择性质。
    
  • 例如：找零问题、活动选择问题、分数背包问题等。
    
  
  

---

6. 经典例题

• LeetCode 455. 分发饼干：
  
  
  
  • 贪心策略：每次满足胃口最小的孩子。
    
  • 代码实现：
    1. int findContentChildren(vector<int>& g, vector<int>& s) {
    2.     sort(g.begin(), g.end());
    3.     sort(s.begin(), s.end());
    4.     int i = 0, j = 0;
    5.     while (i < g.size() && j < s.size()) {
    6.         if (s[j] >= g[i]) {
    7.             i++;
    8.         }
    9.         j++;
    10.     }
    11.     return i;
    12. }

    复制代码
  
  
• LeetCode 122. 买卖股票的最佳时机 II：
  
  
  
  • 贪心策略：每次在价格上涨时买入，价格下跌时卖出。
    
  • 代码实现：
    1. int maxProfit(vector<int>& prices) {
    2.     int profit = 0;
    3.     for (int i = 1; i < prices.size(); i++) {
    4.         if (prices[i] > prices[i - 1]) {
    5.             profit += prices[i] - prices[i - 1];
    6.         }
    7.     }
    8.     return profit;
    9. }

    复制代码
  
  

---

通过把握贪心算法的头脑和经典问题，可以高效解决很多优化问题。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。