Cplusplus利用贪心算法实现找零钱问题

### 回答1：
贪心算法是一种常用的求解找零钱问题的方法。

在 C++ 中，可以先将所有可用的硬币按面额从大到小排序。然后，每次从大到小遍历这些硬币，并在能使用时尽量多地使用较大的硬币。这样可以保证使用的硬币数量最少。

具体实现方法如下：

1. 定义一个数组 coins[] 存储所有可用的硬币面额，并将其按面额从大到小排序。

2. 定义变量 rem 存储当前剩余的找零金额，从 rem 开始从大到小遍历 coins[] 数组。

3. 在能使用时，尽量多地使用较大的硬币。具体来说，对于当前遍历到的硬币 coins[i]，如果 rem>=coins[i]，就使用 coins[i] 凑出 rem 的金额，并将 rem 减去使用的硬币面额。

4. 如果遍历完 coins[] 数组后，rem 仍然大于 0，则表明无法凑出所需的金额，可以输出提示信息并结束程序。

以下是 C++ 代码示例：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;  // 硬币种类数
int coins[N];  // 硬币面额

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> coins[i];

    sort(coins, coins + n, greater<int>());  // 从大到小排  

### 回答2：
贪心算法是一种在每个阶段都选择当前最优解从而达到全局最优解的策略。在找零钱问题中，我们需要找到最少的零钱来凑出一个给定的金额。

首先，我们需要确定一些零钱面额。假设我们有面额为1、2、5、10的零钱。

然后，我们需要计算需要找零的金额和找零的个数。假设需要找零的金额为18元。

接下来，我们可以利用贪心策略来找零钱。首先，我们先找面额为10的零钱，能够找到1个10元，剩余金额为8元。然后，我们再找面额为5的零钱，能够找到1个5元，剩余金额为3元。最后，我们再找面额为1的零钱，需要找3个1元。

通过贪心算法，我们找零的零钱组合为10元+5元+1元+1元+1元，一共需要找5个零钱。

需要注意的是，贪心算法并不能保证得到的解一定是最优解。在某些情况下，贪心算法可能会得到次优解或者不正确的解。因此，在使用贪心算法解决问题时，需要根据具体情况进行判断和分析，并在实际应用中进行验证和调整。  

### 回答3：
贪心算法是一种通过每一步局部最优选择来达到全局最优解的算法。在找零钱问题中，我们希望给定一个金额，用最少的硬币找零。C++可以利用贪心算法来实现这一问题。

首先，我们需要准备一个硬币面额数组，按照从大到小的顺序排列。例如，美国常用的硬币面额可以是[25, 10, 5, 1]，表示25美分、10美分、5美分和1美分的硬币。

然后，我们使用一个变量count来记录找零所需的硬币数量，初始化为0。接下来，我们通过一个循环遍历硬币面额数组，对每个面额进行以下操作：

1. 将面额面值除以当前硬币面额，得到当前面额需要的硬币数量num。

2. 将count加上num，表示增加num个硬币。

3. 将面额面值取余当前硬币面额，得到剩余的金额。如果剩余金额为0，则找零结束，返回count。

4. 如果剩余金额不为0，则继续下一次循环，考虑下一个硬币面额。

最后，如果找零结束时剩余金额仍不为0，则说明没有合适的硬币面额可以找零，返回-1表示无法找零。

下面是利用贪心算法实现找零钱问题的C++代码示例：

#include <iostream>
#include <vector>

int changeCoins(std::vector<int>& coins, int amount) {
int count = 0;
for (int i = 0; i < coins.size(); i++) {
int num = amount / coins[i];
count += num;
amount %= coins[i];
if (amount == 0) {
return count;
}
}
return -1;
}

int main() {
std::vector<int> coins = {25, 10, 5, 1};
int amount = 39;
int minCoins = changeCoins(coins, amount);
std::cout << "最小找零硬币数量：" << minCoins << std::endl;
return 0;
}

以上代码中，我们将硬币面额设置为[25, 10, 5, 1]，需要找零的金额为39。运行程序后，会输出最小找零硬币数量为7。