贪心算法零钱找回问题c++代码
时间: 2023-10-02 13:06:21 浏览: 60
以下是贪心算法解决零钱找回问题的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void change(vector<int>& coins, int amount) {
sort(coins.begin(), coins.end()); // 从小到大排序
int n = coins.size();
int cnt = 0;
for (int i = n - 1; i >= 0; i--) { // 从大到小遍历硬币
while (amount >= coins[i]) { // 如果当前硬币可以用来找钱
amount -= coins[i]; // 找钱
cnt++; // 计数器加一
}
}
if (amount == 0) {
cout << cnt << endl; // 输出最少硬币数
} else {
cout << "无法找零" << endl;
}
}
int main() {
vector<int> coins{1, 2, 5, 10, 20, 50};
int amount = 68;
change(coins, amount);
return 0;
}
```
其中,`coins` 为硬币面值数组,`amount` 为需要找零的金额。`change` 函数中,我们先将硬币面值从小到大排序,然后从大到小遍历硬币,每次找到一个硬币可以用来找钱,就计数器加一,直到找完所有的零钱或者无法找零。最后,如果找完所有的零钱,就输出最少硬币数,否则输出 "无法找零"。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)