Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal ini.
Secara Harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanayak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, Prinsip Greedy adalah take what you can get now. Dalam kehidupan sehari hari Greedy dapat digunakan dalam masalah seperti :
- Memilih beberapa jenis investasi
- Mencari jalur tersingkat
- Maksimasi (maxizimation)
- Minimasi (minimization)
Contoh : tersedia banyak koin 1, 5, 10, 25
Uang senilai A= 32 dapat ditukar dengan banyak cara berikut:
32 = 1 + 1 + …+ 1 (32 koin)
32 = 5 + 5 + 5 + 5 + 10 + 1 + 1(7 koin)
32 = 10 + 10 + 10 + 1 + 1(5 koin)…dst
## Minimum: 32 = 25 + 5 + 1 + 1 (4 koin)
Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam urutan yang menurun (noninceasing order).
Jika himpunan koin sudah terurut menurun, maka kompleksitas algoritma greedy = O(n).
Sayangnya, algoritma greedy untuk masalah penukaran uang ini tidak selalu menghasilkan solusi optimal.
0 comments:
Post a Comment