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

貪欲アルゴリズムは、特定の問題に対する最適な解決策を見つけるために使用されるアルゴリズムです。貪欲アルゴリズムは、各部分の局所的な最適解 (問題の一部に対する最適解) を見つけることによって機能し、全体的な最適解が見つかることを示します。

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

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

例 1 -

Input : 1231
Output : 7

手順 - 500 ルピー紙幣が 2 枚必要です。 100ルピー紙幣、20ルピー紙幣1枚、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

以上が最小コイン数を見つける貪欲アルゴリズム用の C/C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。