C++ 中的贪心算法及其实现

在本文中，我们将介绍C++中的贪心算法的概念、原理以及实现方法。贪心算法是一种常用的优化算法，常被用于解决最优化问题。所谓贪心算法，即每一步都选择当前最优解，希望最终得到全局最优解。

阅读更多：C++ 教程

贪心算法的概念

贪心算法是一种简单而有效的算法思想，其核心思想是每次都做出在当前情况下最优的选择，以期望最后达到全局最优。贪心算法通常适用于一类特殊问题，即问题具有贪心选择性质和最优子结构性质。

贪心选择性质：即每一步的最优解可以导致全局最优解。

最优子结构性质：即问题的最优解可以由其子问题的最优解推导出来。

贪心算法的实现

贪心算法的实现通常包含以下几个步骤：

确定问题的贪心选择。即每一步都做出的最优选择。
利用贪心选择构造问题的最优解。
证明贪心选择是全局最优解。

下面通过几个经典的问题来介绍贪心算法的具体实现。

1. 零钱兑换问题

问题描述：给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额所需的最少的硬币个数。可以假设每种硬币的数量是无限的。

int coinChange(vector<int>& coins, int amount) {
    sort(coins.rbegin(), coins.rend());
    int res = INT_MAX;
    coinChangeDFS(coins, amount, 0, 0, res);
    return res == INT_MAX ? -1 : res;
}

void coinChangeDFS(vector<int>& coins, int amount, int start, int cnt, int& res) {
    if (amount == 0) {
        res = min(res, cnt);
        return;
    }
    if (start == coins.size()) {
        return;
    }
    for (int k = amount / coins[start]; k >= 0 && k + cnt < res; k--) {
        coinChangeDFS(coins, amount - k * coins[start], start + 1, cnt + k, res);
    }
}

2. 区间调度问题

问题描述：给定多个区间，计算出这些区间中最多有多少个互不重叠的区间。区间调度问题中，要求选择尽可能多的互不重叠的区间。

int intervalSchedule(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return 0;
    }
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });
    int end = intervals[0][1];
    int cnt = 1;
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] >= end) {
            end = intervals[i][1];
            cnt++;
        }
    }
    return cnt;
}

3. 分糖果问题

问题描述：给定一组孩子的评分以及一定数量的糖果，每个孩子至少分到一个糖果，且评分更高的孩子必须比他的邻居们分得更多的糖果。问最少需要准备多少个糖果。

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    int res = candies[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = max(candies[i], candies[i + 1] + 1);
        }
        res += candies[i];
    }
    return res;
}