贪婪算法的C / C ++程序，用于查找最小数量的硬币
贪婪算法是用于找到给定问题的最优解的算法。贪心算法通过找到每个部分的局部最优解（问题的一部分的最优解）来工作，因此表明可以找到全局最优解。
在这个问题中，我们将使用贪婪算法来查找可以补足给定总和的最小硬币/纸币数。为此，我们将考虑所有有效的硬币或纸币，例如{1，2，5，10，20，50，100，200，500，2000}的面额。并且我们需要返回这些硬币/纸币的数量，我们需要补足总数。
让我们举几个例子来更好地理解上下文-
示例1-
Input : 1231 Output : 7
说明-我们将需要两张500卢比的钞票，两张100卢比的钞票，一张20卢比的钞票，一张10卢比的钞票和一张Re1硬币。总计2+2+1+1+1=7
示例2-
Input : 2150 Output : 3
说明-我们将需要一张2000卢比的钞票，一张100卢比的钞票和一张50卢比的钞票。
为了使用贪婪算法解决此问题，我们将发现哪个是可以使用的最大面额。然后我们将从总和中减去最大面额，然后再次执行相同的过程，直到总和变为零。
算法
Input: sum, Initialise the coins = 0 Step 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 Sum Step 3: Repeat step 2 until the sum becomes 0. Step 4: Print each value in coins.
示例
#include <bits/stdc++.h>
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<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 << "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 is 2000 500 500 200 50 2 1