C++ 算法精讲之贪心算法

C++ 算法精讲之贪心算法攻略

什么是贪心算法

贪心算法是指在求解问题时，先做出在当前看来最优的选择，而无需考虑到未来的情况。贪心算法的应用范围很广泛，常应用于最优化问题中。

贪心算法的基本思想

在贪心算法中，每次选择的步骤都是基于当前状态下的最优选择，也就是选取局部最优解，而不考虑整体最优解的条件，在获得当前最优解的情况下逐步推进，最终获得整体最优解。

贪心算法的使用条件

在使用贪心算法解决问题的时候，我们需要满足贪心算法的使用条件：

1. 问题的最优解可以通过选择局部最优解来获得；
2. 问题的子问题的最优解也是可以通过选择局部最优解来获得的，这样可以将问题化解为子问题，通过贪心逐步解决。

贪心算法的实现步骤

贪心算法在具体实现的时候，需要考虑以下步骤：

1. 确定问题的“贪心选择性质”，即确定每步选择后该问题所有可能的解都可以通过局部最优选择来获得；
2. 构造问题的贪心选择；
3. 证明贪心选择是最优的，通过数学公式、归纳法、反证法等方法证明；
4. 将贪心选择和原问题的结合起来，构建整体解。

贪心算法的实例

示例1: 买卖股票问题

假设你有一只股票的历史价格数组prices，你需要选择一个时间点买入股票，并在未来的某一个时间售出。已知你不能同时拥有多只股票，也就是你需要在卖出之前再买入。请问你最多可以赚取多少利润？

思路：

我们可以贪心地选择，每次选择前一天到当天，如果获利，则加入利润，继续向后找。

代码实现：

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;
}

示例2: 分配饼干

假设你有一些饼干，每个饼干的大小都不一样。你现在有一些孩子，每个孩子的贪心值（需要饼干的大小）也不一样。请问，你至少要准备多少个饼干才能让所有孩子都满足呢？

思路：

贪心地选择，对于每个孩子，都选取能满足他贪心值的最小饼干。

代码实现：

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int count = 0;
    for (int i = 0, j = 0; i < g.size() && j < s.size(); j++) {
        if (g[i] <= s[j]) {
            count++;
            i++;
        }
    }
    return count;
}

总结

贪心算法是一种非常实用的算法，在最优化问题中很常用。在使用贪心算法时，需要满足贪心算法的使用条件，并按照贪心算法实现步骤进行处理和转化。本文介绍了贪心算法的基本思想、实现步骤和两个实例，相信读者已经对贪心算法有了更加完整和深刻的理解。