Rumah > pembangunan bahagian belakang > C++ > Program C/C++ untuk algoritma tamak untuk mencari bilangan minimum syiling

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

PHPz
Lepaskan: 2023-09-19 23:01:02
ke hadapan
1062 orang telah melayarinya

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
Salin selepas log masuk

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
Salin selepas log masuk

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.
Salin selepas log masuk

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;
}
Salin selepas log masuk

Output

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

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!

sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan