贪心算法是一种用于寻找给定问题的最优解决方案的算法。贪婪算法的工作原理是找到每个部分的局部最优解（问题的一部分的最优解），因此表明可以找到全局最优解。
在这个问题中，我们将使用贪婪算法算法来找到可以组成给定总和的最小硬币/纸币数量。 为此，我们将考虑所有有效的硬币或纸币，即面额为 { 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
立即学习“C++免费学习笔记（深入）”；
示例 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.
示例
实时演示
#includeusing 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 is 2000 500 500 200 50 2 1
