【C++】贪心算法

贪心算法（Greedy Algorithm）是一种基于贪心策略的算法，它在每一步选择中都采取当前状态下最优的选择，以希望最终得到全局最优解。贪心算法通常适用于满足最优子结构性质的问题，即问题的最优解可以通过其子问题的最优解来构造。

贪心算法的基本思路是：

1. 定义问题的目标函数，即要最大化或最小化的目标。
2. 将问题分解为若干个子问题。
3. 对每个子问题进行求解，选择当前最优解。
4. 将每个子问题的最优解合并成原问题的解。

贪心算法的关键在于贪心策略的选择，即在每一步如何选择当前的最优解。这种选择要考虑问题的特性和约束条件，以确保选择的最优解能够导致全局最优解。

贪心算法的案例：找零钱问题（Coin Change Problem）

假设你是一个收银员，需要找零给客户。现有不同面额的硬币，包括 1 元、2 元、5 元、10 元。对于任意金额的找零，你需要找出所需的最少硬币数量。

贪心算法解决这个问题的策略是每次找零时选择面额最大的硬币，直到找完所有金额。具体步骤如下：

1. 初始化所需找零金额为 x。
2. 选择面额最大的硬币 c，使得 c <= x。
3. 找出 x 中可以使用硬币 c 的最大数量 k。
4. 更新 x =x - c * k。 如果 x 不为 0，则继续执行步骤 2；否则结束。

以下是一个示例代码来解决找零钱问题：

#include <iostream>
#include <vector>

std::vector<int> coinChange(int amount, std::vector<int>& coins) {
    std::vector<int> result;
    
    // 从大到小排序硬币面额
    std::sort(coins.rbegin(), coins.rend());
    
    for (int i = 0; i < coins.size(); i++) {
        while (amount >= coins[i]) {
            result.push_back(coins[i]);
            amount -= coins[i];
        }
    }
    
    if (amount != 0) {
        // 无法凑出指定金额
        result.clear();
    }
    
    return result;
}

int main() {
    int amount = 18;
    std::vector<int> coins = {10, 5, 2, 1};
    
    std::vector<int> result = coinChange(amount, coins);
    
    if (result.empty()) {
        std::cout << "Cannot make change for the given amount." << std::endl;
    } else {
        std::cout << "The minimum number of coins required: " << result.size() << std::endl;
        std::cout << "Coins used: ";
        for (int i = 0; i < result.size(); i++) {
            std::cout << result[i] << " ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

在上面的代码中，coinChange 函数接收一个金额和硬币面额的向量作为输入。它首先对硬币进行从大到小的排序，然后根据贪心策略依次选择面额最大的硬币，并计算所需硬币的数量。最后，返回所需硬币的向量。

在示例中，我们找零 18 元，使用的硬币面额是 {10, 5, 2, 1}。输出结果为：

The minimum number of coins required: 4
Coins used: 10 5 2 1
这表示我们需要使用 4 枚硬币（10 元、5 元、2 元和 1 元）来找零 18 元。

需要注意的是，贪心算法并不适用于所有问题，有些问题可能无法得到最优解。因此，在使用贪心算法时需要仔细分析问题的性质和约束条件，确保贪心策略的正确性。