贪心算法是一种用于寻找给定问题的最优解决方案的算法。贪婪算法的工作原理是找到每个部分的局部最优解（问题的一部分的最优解），因此表明可以找到全局最优解。
在这个问题中，我们将使用贪婪算法算法来找到可以组成给定总和的最小硬币/纸币数量。 为此，我们将考虑所有有效的硬币或纸币，即面额为 { 1, 2, 5, 10, 20, 50 , 100, 200 , 500 ,2000 }。我们需要返回需要补足总和的硬币/纸币的数量。
让我们举几个例子来更好地理解上下文 –
示例 1 –
Input : 1231Output : 7
说明 – 我们需要两张 500 卢比纸币、两张 100 卢比纸币、一张 20 卢比纸币、一张 10 卢比纸币和一张 Re 1 硬币。总计为 2+2+1+1+1 = 7
立即学习“C++免费学习笔记（深入）”；
示例 2 –
Input : 2150Output : 3
说明 – 我们需要一张 2000 卢比纸币、一张 100 卢比纸币和一张 50 卢比纸币。
为了使用贪心算法解决此问题，我们将找到最大面额的纸币可以使用。然后我们将从总和中减去最大面额，并再次执行相同的过程，直到总和为零。
算法
Input: sum,Initialise the coins = 0Step 1: Find the largest denomination that can be used i.e. smaller than sum.Step 2: Add denomination two coins and subtract it from the SumStep 3: Repeat step 2 until the sum becomes 0.Step 4: Print each value in coins.
示例
实时演示
#include using namespace std;int notes[] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 };int n = sizeof(notes) / sizeof(notes[0]);void minchange(int sum){ vector coins; for (int i = n - 1; i >= 0; i--) { while (sum >= notes[i]) { sum -= notes[i]; coins.push_back(notes[i]); } } for (int i = 0; i < coins.size(); i++) cout << coins[i] << "t";}int main(){ int n = 3253; cout << "The minimum number of coins/notes that sum up " << n << " is t "; minchange(n); return 0;}
输出
The minimum number of coins/notes that sum up 3253 is2000 500 500 200 50 2 1
以上就是贪心算法的C/C++程序，用于找到最少硬币数量的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445522.html
微信扫一扫 
支付宝扫一扫 
