贪心算法是一种用于寻找给定问题的最优解决方案的算法。贪婪算法的工作原理是找到每个部分的局部最优解（问题的一部分的最优解），因此表明可以找到全局最优解。
在这个问题中，我们将使用贪婪算法算法来找到可以组成给定总和的最小硬币/纸币数量。 为此，我们将考虑所有有效的硬币或纸币，即面额为 { 1, 2, 5, 10, 20, 50 , 100, 200 , 500 ,2000 }。我们需要返回需要补足总和的硬币/纸币的数量。
让我们举几个例子来更好地理解上下文 -
示例 1 -
Input : 1231
Output : 7
说明 - 我们需要两张 500 卢比纸币、两张 100 卢比纸币、一张 20 卢比纸币、一张 10 卢比纸币和一张 Re 1 硬币。总计为 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
.........................................................