貪心演算法的C/C++程序，用於找到最少硬幣數量

貪心演算法是一種用於尋找給定問題的最優解決方案的演算法。貪婪演算法的工作原理是找到每個部分的局部最優解（問題的一部分的最優解），因此表明可以找到全局最優解。

在這個問題中，我們將使用貪婪演算法演算法來找到可以組成給定總和的最小硬幣/紙幣數量。 為此，我們將考慮所有有效的硬幣或紙幣，即面額為 { 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 = 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

以上是貪心演算法的C/C++程序，用於找到最少硬幣數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！