Program C/C++ untuk algoritma tamak untuk mencari bilangan minimum syiling

Algoritma tamak ialah algoritma yang digunakan untuk mencari penyelesaian optimum kepada masalah yang diberikan. Algoritma tamak berfungsi dengan mencari penyelesaian optimum tempatan untuk setiap bahagian (penyelesaian optimum untuk satu bahagian masalah), dengan itu menunjukkan bahawa penyelesaian optimum global boleh ditemui.

Dalam masalah ini kita akan menggunakan algoritma Algoritma Greedy untuk mencari bilangan minimum syiling/nota yang boleh membentuk jumlah tertentu. Untuk ini, kami akan mempertimbangkan semua syiling atau wang kertas yang sah, iaitu denominasi { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}. Kita perlu mengembalikan bilangan syiling/nota yang diperlukan untuk menjumlahkan jumlah tersebut.

Mari kita berikan beberapa contoh untuk memahami konteks dengan lebih baik -

Contoh 1 -

Input : 1231
Output : 7

Penjelasan - Kami memerlukan dua not 500 rupee, dua not 100 rupee, satu not 20 rupee dan satu not bank 1 Semula 1 syiling. Jumlahnya ialah 2+2+1+1+1 = 7

Contoh 2 -

Input : 2150
Output : 3

Arahan - Kami memerlukan satu not Rs 2000, satu not Rs 100 dan satu not Rs 50.

Untuk menyelesaikan masalah ini menggunakan algoritma tamak, kami akan mencari wang kertas denominasi terbesar yang boleh digunakan. Kami kemudian akan menolak denominasi maksimum daripada jumlah dan melakukan proses yang sama sekali lagi sehingga jumlahnya adalah sifar.

Algoritma

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.

Contoh

Demonstrasi masa nyata

#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;
}

Output

The minimum number of coins/notes that sum up 3253 is
2000 500 500 200 50 2 1

Atas ialah kandungan terperinci Program C/C++ untuk algoritma tamak untuk mencari bilangan minimum syiling. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!