コインの最小数を見つけるための欲張りアルゴリズムのためのC/C++プログラム

欲張りアルゴリズムは、与えられた問題の最適な解決策を見つけるために使用されるアルゴリズムです。欲張りアルゴリズムは、各部分の局所的に最適な解（問題の一部に対する最適な解）を見つけることによって機能するため、グローバルな最適解が見つかる可能性があることを示します。

この問題では、欲張りアルゴリズムを使用して、指定された合計を構成できるコイン/ノートの最小数を見つけます。 このために、すべての有効な硬貨または紙幣、つまり{1、2、5、10、20、50、100、200、500、2000}の金種を考慮します。そして、合計を補うために必要なこれらのコイン/ノートの数を返す必要があります。

コンテキストをよりよく理解するために、いくつかの例を見てみましょう-

例1-

Input : 1231
Output : 7

説明 − Rs 500紙幣2枚、Rs 100紙幣2枚、Rs 20紙幣1枚、Rs 10紙幣1枚、Re1コイン1枚が必要です。合計すると2+2 + 1 + 1 + 1 =7

例2-

Input : 2150
Output : 3

説明-2000ルピー紙幣1枚、100ルピー紙幣1枚、50ルピー紙幣1枚が必要です。

欲張りアルゴリズムを使用してこの問題を解決するために、使用できる最大の金種であるを見つけます。次に、合計から最大の金額を引き、合計がゼロになるまで同じプロセスを繰り返します。

アルゴリズム

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