Metode Greedy

Metode greedy adalah metode yang digunakan untuk memecahkan persoalan optimasi, ada 2 macam persoalan optimasi, yaitu maksimasi dan minimasi, artinya dengan metode greedy kita bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang ada.

arti kata greedy sendiri adalah RAKUS, namun maksud dari metode grredy adalah kita melihat solusi optimal lokal, atau solusi optimal yang tampak didepan mata, dengan harapan mendapatkan solusi optimal secara global atau secara keseluruhan

Contohnya adalah pada kasus penukaran uang, misalkan kita memiliki uang senilai 32 dan akan kita tukarkan dengan koin, uang koin pecahan yang tersedia adalah 1, 5, 10, 25, jika kita mengharapkan agar pecahan yang kita miliki sedikit mungkin maka kita bisa menggunakan metode greedy dengan cara memilih pecahan terbesar terlebih dahulu. mari kita lihat


uang 32.
pecahan 1,5,10,25
dengan metode greedy kita harus memilih pecahan terbesar terlebih dahulu yaitu 25, kemudian baru mengambil sampai sesuai dengan uang yang kita miliki.
yaitu= 25+5+1+1=32(4 koin)
sebenarnya ada beberapa alternatif solusi pemecahan masalah diatas sebagai berikut

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

Dalam hal ini metode greedy berhasil mendapat kan hasil maksimal secara global atau secara keseluruhan dengan mengambil koin yang terbesar terlebih dahulu.

Namun ada kalanya metode greedy gagal mendapatkan solusi optimal, hal ini juga dikarenakan oleh sifat metode greedy itu sendiri yang memperhatikan keuntungan lokal(diawal) tanpa memperhatikan kemungkinan solusi yang lain, contoh:

Uang yang ditukar sebesar 7
Koin yang tersedia 5,4,3, dan 1

jika kita menukarkan uang tersebut dengan metode greedy maka kita harus mengambil pecahan terbesar lebih dulu yaitu 5, baru kemudian kita memilih pecahan berikutnya hingga genap berjumlah 7

7=5+1+1 (3koin)

alternatif solusi
7=4+3 (2koin)

pada contoh diatas jelas terlihat bahwa metode greedy gagal memberikan solusi optimal.


Untuk mata uang dollar AS, euro Eropa, dan crown Swedia, algoritma greedy selalu memberikan solusi   optimum. Misalnya untuk menukarkan $6,39 dengan uang kertas (bill) dan koin sen (cent), kita dapat memilih:
•Satu buah uang kertas senilai $5
•Satu buah uang kertas senilai $1 ($5 + $1 = $6))
•Satu koin  25 sen ($5 + $1 + 25c = $6,25)
•Satu koin 10 sen ($5 + $1 + 25c + 10c = $6,35)
•Empat koin 1 sen ($5 + $1 + 25c + 10c + 1c + 1c + 1c + 1c = $6,39)

Bagaimana dengan mata uang rupiah Indonesia?


Metode greedy dipakai dalam masalah
1.Optimal On tape Storage Problem
2.Knapsack Problem
3.Minimum Spanning Tree Problem
4.Shortest Path Problem