Pengertian Algoritma Greedy
Algoritma Greedy merupakan metode yang populer untuk memecahkan persoalan optimasi. Algortima greedy membentuk solusi langkah per langkah (step by step) dan pada setiap langkah terdapat banyak pilihan untuk dieksplorasi. Oleh karena itu dalam setiap langkah diperlukan keputusan terbaik dalam menentukan pilihan. Algoritma greedy memiliki prinsip yaitu, "take what you get now" dengan kata lain greedy itu rakus atau tamak. Greedy memiliki 2 optimasi yaitu, Maximization (maksimal) dan Minimization (minimum).
Elemen - Elemen Greedy :
1. Himpunan Kandidat
2. Himpunan Solusi
3. Fungsi Seleksi
4. Fungsi Kelayakan
5. Fungsi Obyektif
Contoh Kasus Algoritma Greedy
Kasus penukaran uang:
Diberikan uang senilai 8500. Tukar 8500 dengan koin - kooin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
Jawab: Tersedia banyak koin 500, 1000, 2000, 5000
Uang senilai 8500 dapat ditukar dengan banyak cara berikut:
8500 = 500 + 500 + 500 +...+ 500 (17 Koin)
8500 = 1000 + 1000 + 1000 + 1000 + 1000 + 1000 + 1000 + 1000 + 500 ( 9 Koin)
8500 = 2000 + 2000 + 2000 + 1000 + 500 + 500 + 500 ( 7 Koin)
|
|
dst.
8500 = 5000 + 2000 + 1000 + 500 ( 4 Koin) --> Minimum
Contoh Algoritma Greedy
Algoritma TukarUang(input
C : himpunan_koin, A :
integer)à himpunan_koin
{ Menghasilkan koin-koin dengan
total nilai = A dengan jumlah
minimum}
Deklarasi
x : koin
S : himpunan_koin
Algoritma
S ß {}
while (jumlah
nilai
semua
koin
dalam
S <> A ) AND (C
<> {}) do
x ß koin dengan nilai terbesar
C ß C –
{x}
if (jumlah nilai semua koin dalam S) +
nilai koin x < A then
S ß S U
{x}
endif
endwhile
if (jumlah nilai semua koin dalam S) =
A then
return S
else
write(‘tidak ada solusi’);
endfor