景征网站建设/网址缩短在线生成器
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优决策的算法思想。它通过局部最优的选择，希望最终达到全局最优解。贪心算法并不总是能得到全局最优解，但在某些问题上非常有效。
1. 贪心算法的核心思想
- 局部最优：在每一步选择中，选择当前状态下最优的决策。
- 无后效性：当前的选择不会影响后续的选择。
- 贪心选择性质：通过局部最优选择，最终能够得到全局最优解。
2. 贪心算法的适用条件
贪心算法适用于满足以下条件的问题：
- 最优子结构：问题的最优解包含子问题的最优解。
- 贪心选择性质：通过局部最优选择，能够得到全局最优解。
3. 贪心算法的经典问题
1. 找零问题
- 问题描述：给定不同面额的硬币和一个总金额，求最少需要多少硬币。
- 贪心策略：每次选择面额最大的硬币。
- 代码实现：
int coinChange(vector<int>& coins, int amount) {sort(coins.rbegin(), coins.rend()); // 按面额从大到小排序int count = 0;for (int coin : coins) {while (amount >= coin) {amount -= coin;count++;}}return amount == 0 ? count : -1; // 如果无法凑出金额，返回 -1 }
2. 活动选择问题
- 问题描述：给定一组活动，每个活动有开始时间和结束时间，求最多能安排多少个互不冲突的活动。
- 贪心策略：每次选择结束时间最早的活动。
- 代码实现：
int maxActivities(vector<pair<int, int>>& activities) {sort(activities.begin(), activities.end(), [](const pair<int, int>& a, const pair<int, int>& b) {return a.second < b.second; // 按结束时间排序});int count = 1;int last_end = activities[0].second;for (int i = 1; i < activities.size(); i++) {if (activities[i].first >= last_end) {count++;last_end = activities[i].second;}}return count; }
3. 背包问题（分数背包）
- 问题描述：给定一组物品，每个物品有重量和价值，背包有容量限制，求能装入的最大价值（物品可以分割）。
- 贪心策略：每次选择单位重量价值最高的物品。
- 代码实现：
double fractionalKnapsack(int capacity, vector<pair<int, int>>& items) {sort(items.begin(), items.end(), [](const pair<int, int>& a, const pair<int, int>& b) {return (double)a.second / a.first > (double)b.second / b.first; // 按单位重量价值排序});double max_value = 0;for (auto& item : items) {if (capacity >= item.first) {capacity -= item.first;max_value += item.second;} else {max_value += (double)item.second / item.first * capacity;break;}}return max_value; }
4. 贪心算法的局限性
贪心算法并不总是能得到全局最优解。例如：
- 0-1 背包问题：物品不能分割，贪心算法无法得到最优解。
- 最短路径问题：Dijkstra 算法是贪心算法，但不适用于负权边。
5. 贪心算法的总结
- 优点：
- 简单易实现。
- 时间复杂度通常较低。
- 缺点：
- 不适用于所有问题。
- 无法保证全局最优解。
- 适用场景：
- 问题具有最优子结构和贪心选择性质。
- 例如：找零问题、活动选择问题、分数背包问题等。
6. 经典例题
-
LeetCode 455. 分发饼干：
- 贪心策略：每次满足胃口最小的孩子。
- 代码实现：
int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0, j = 0;while (i < g.size() && j < s.size()) {if (s[j] >= g[i]) {i++;}j++;}return i; }
-
LeetCode 122. 买卖股票的最佳时机 II：
- 贪心策略：每次在价格上涨时买入，价格下跌时卖出。
- 代码实现：
int maxProfit(vector<int>& prices) {int profit = 0;for (int i = 1; i < prices.size(); i++) {if (prices[i] > prices[i - 1]) {profit += prices[i] - prices[i - 1];}}return profit; }
通过掌握贪心算法的思想和经典问题，可以高效解决许多优化问题。