Penerapan Algoritma Greedy dalam Penukaran Uang

Selamat pagi teman - teman, kali ini saya akan posting mengenai Algoritma Greedy dalam Penukaran Uang..

Sebelumnya, Algoritma Greedy adalah metode yang populer untuk memecahkan persoalan mengenai optimasi(mencari nilai paling optimum).

Optimum disini yaitu :

• Maksimasi(maximization)
• Minimasi(minimization)

Nah, selain itu Algoritma Greedy mempunyai prinsip "take what you can get now". Dikatakan seperti itu karena memang arti kata Greedy adalah rakus, tamak dan lain sebagainya..

 

Pada setiap langkahnya, algoritma ini kita diminta untuk membuat pilihan optimum lokal dengan harapan bahwa langkah selanjutnya akan mengarah kepada solusi optimum global

Contoh singkat persoalan Penukaran Uang

Strategi Greedy : bahwa pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang tersisa

Misalkan : A=32(koin yang akan ditukarkan) dan koin yang tersedia adalah dengan pecahan : 1,5,10 dan 25.

• langkah 1 : Pilih 1 buah koin 25 (total sekarang = 25)
• langkah 2 : Pilih 1 buah koin 5   (total sekarang = 25 + 5 = 30)
• langkah 3 : Pilih 2 buah koin 1   (total sekarang = 25 + 5 + 1 + 1 = 32)

Solusi yang ditemukan adalah optimum, dengan jumlah koin pecahan = 4 (paling sedikit).

Materi lengkap dapat dilihat Strategi Algoritma

Contoh program bisa di lihat disini . 

Semoga dapat bermanfaat bagi teman - teman..

Source Code Penukaran Pecahan Uang

Selamat pagi teman - teman.. kali ini saya akan share source code untuk Penukaran Pecahan Uang dalam Rupiah..

Tetapi disini, pecahan uangnya saya inisialisasi kan dahulu.. jadi tergantung dengan kebutuhan..
Silahkan di cek, dan dipelajari..


#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main(int argc, char** argv) {
int x,a,b,c,d,e,f,g,h;
int p = 20000, q = 10000, r = 5000, s = 1000;
cout<<"masukkan jumlah uang : ";
cin>>x;
a = x / p;
b = x % p;
c = b / q;
d = b % q;
e = d / r;
f = d % r;
g = f / s;
h = f % s;
if(a!=0){
cout<<a<<" lembar 20.000 an"<<endl;
}
if(c!=0){
cout<<c<<" lembar 10.000 an"<<endl;
}
if(e!=0){
cout<<e<<" lembar 5.000 an"<<endl;
}
if(f!=0){
cout<<g<<" lembar 1.000 an"<<endl;
}
return 0;
}

Semoga bermanfaat teman - teman.. :)