Algoritma Greedy

Algoritma Greedy merupakam metode yang paling populer untuk memecahkan persoalan optimasi. Persoalan optimasi (optimization problems) à persoalan mencari solusi optimasi.

Greedy = rakus, tamak, banyak, …

Prinsip Greedy :  “take what you can get now!”.

Algoritma Greedy membentuk solusi langkah per langkah (step by step). Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam membentuk pilihan.

Contoh : Persoalan Optimasi

“Masalah Penukaran Uang”

Diketahui diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

Jawab:  

                                       

Tersedia koin : 1,5, 10, dan 25.

Uang A senilai 32 dapat ditukar dengan cara :

32 = 1 + 1 + 1 + … + 1                         (32 koin)

32 = 5 + 5 + 5 + 5 + 10 + 10 + 1                      (7 koin)

32 = 10 + 10 + 10 + 1 + 1                    ( 5 koin)

Maka, optimasi dari penukaran koin seminimum mungkin yaitu …

32 = 25 + 5 + 1 +                                 (4 koin)