C/C++ 贪婪算法程序用于查找最少硬币数量
cc++server side programmingprogramming
贪婪算法是一种用于为给定问题寻找最佳解决方案的算法。贪婪算法通过寻找每个部分的局部最优解(问题一部分的最优解)来工作，从而表明可以找到全局最优解。
在这个问题中，我们将使用贪婪算法来查找可以构成给定总和的最少硬币/纸币数量。为此，我们将考虑所有有效的硬币或纸币，即面值为 { 1, 2, 5, 10, 20, 50 , 100, 200 , 500 ,2000 }。我们需要返回需要凑足总和的硬币/纸币的数量。
让我们举几个例子来更好地理解上下文 −
示例 1 −
输入:1231 输出:7
解释 − 我们需要两张 500 卢比的纸币、两张 100 卢比的纸币、一张 20 卢比的纸币、一张 10 卢比的纸币和一枚 1 卢比的硬币。总计为 2+2+1+1+1 = 7
示例 2 −
输入:2150 输出:3
解释 −我们需要一张 2000 卢比的钞票、一张 100 卢比的钞票和一张 50 卢比的钞票。
要使用贪婪算法解决这个问题，我们将找到可以使用的最大面额。然后我们将从总和中减去最大面额，并再次执行相同的过程，直到总和变为零。
算法
输入:总和， 初始化硬币 = 0 步骤 1:找到可以使用的最大面额，即小于总和。 步骤 2:将两枚硬币的面额相加并从总和中减去 步骤 3:重复步骤 2，直到总和变为 0。 步骤 4:打印硬币中的每个值。
示例
#include <bits/stdc++.h>
使用命名空间 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<int> 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 << "总计 << n << "的最小硬币/纸币数量为 \t ";
minchange(n);
return 0;
}
输出
总计为 3253 的硬币/纸币数量为 2000 500 500 200 50 2 1
