C/C++ 贪心算法求最小硬币数量程序

贪心算法是一种用于为给定问题找到最优解的算法。贪心算法的工作原理是找到每个部分的局部最优解（问题一部分的最优解），从而显示可以找到全局最优解。

在这个问题中，我们将使用贪心算法来找到可以构成给定总和的最小硬币/钞票数量。 为此，我们将考虑所有有效的硬币或钞票，即面额 { 1, 2, 5, 10, 20, 50 , 100, 200 , 500 ,2000 }。我们需要返回构成总和所需的这些硬币/钞票的数量。

让我们举几个例子来更好地理解上下文 -

示例 1 -

Input : 1231
Output : 7

说明 - 我们将需要两张 500 元的钞票，两张 100 元的钞票，一张 20 元的钞票，一张 10 元的钞票和一枚 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 = 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

sudhir sharma

更新于: 2019-09-19

5K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始学习