找零钱问题贪心算法c++
时间: 2023-08-02 17:29:28 浏览: 67
好的,这是一个经典的贪心算法问题。我们假设有一些硬币,它们的面值为 1,5,10,20,50,100 元。现在需要找给顾客一定数量的零钱,问如何用最少的硬币数找给顾客?
我们可以使用贪心算法来解决这个问题。具体做法如下:
1. 首先将硬币按面值从大到小排序。
2. 从面值最大的硬币开始,不断地用当前面值的硬币去尽量多地找零,直到找完或者不能再找为止。然后再用下一个面值的硬币去找零,以此类推。
3. 直到找完所有需要找的零钱为止。
下面是 C++ 的代码实现:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> coins = {100, 50, 20, 10, 5, 1}; // 硬币面值
vector<int> change(int n) {
vector<int> result;
for (int i = 0; i < coins.size() && n > 0; i++) {
while (n >= coins[i]) {
result.push_back(coins[i]);
n -= coins[i];
}
}
return result;
}
int main() {
int n = 123;
vector<int> result = change(n);
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
return 0;
}
```
这里我们定义一个 `change` 函数,它接受一个正整数 `n`,表示需要找的零钱数,返回一个由硬币面值组成的向量 `result`,表示找零的方案。在函数中,我们按照硬币面值从大到小的顺序循环,每次用当前面值的硬币尽量多地找零,直到找完或者不能再找为止。最后返回找零方案即可。
注意,这个贪心算法的正确性是显然的,因为每次都使用当前面值的硬币尽量多地找零,所以能够保证找到最优解。