METODE GREEDY

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

 

Berikut Contoh soal dan Jawaban Greedy

 

1.   Diketahui 4 program yang akan disimpan dalam media penyimpanan dengan panjang masing-masing 6, 8, 4, dan 2. Bagaimana proses penyimpanan yang optimal dengan metode greedy?

Diketahui :

N : 4 

Yaitu : 4! : 4*3*2*1 = 24 Cara

6,8,4,2

 

1	2	3	4	=	6	14	18	20	58
1	2	4	3	=	6	14	16	20	56
1	3	2	4	=	6	10	18	20	54
1	3	4	2	=	6	8	16	20	50
1	4	2	3	=	6	8	12	20	46
1	4	3	2	=	6	10	12	20	48
2	1	3	4	=	8	14	18	20	60
2	3	1	4	=	8	12	18	20	58
2	4	1	3	=	8	10	16	20	54
2	1	4	3	=	8	14	16	20	58
2	4	3	1	=	8	10	14	20	52
2	3	4	1	=	8	12	14	20	54
3	2	1	4	=	4	12	18	20	54
3	2	4	1	=	4	12	14	20	50
3	1	4	2	=	4	10	12	20	46
3	1	2	4	=	4	10	18	20	52
3	4	1	2	=	4	6	12	20	42
3	4	2	1	=	4	6	14	20	44
4	1	2	3	=	2	8	16	20	46
4	2	3	1	=	2	10	14	20	46
4	3	2	1	=	2	6	14	20	42
4	1	3	2	=	2	8	12	20	42
4	2	1	3	=	2	10	16	20	48
4	3	1	2	=	2	6	12	20	40

 

 

 

 

 

 

               

2.      Diketahui 4 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 30 Kg. Berat masing-masing barang adalah 15 Kg, 10 Kg, 18 Kg dan 20 Kg dimana setiap barang memiliki profit sebesar masing-masing 20, 25, 9, dan 15. Tentukan barang mana saja yang dapat disimpan ke dalam tempat penyimpanan sehingga diperoleh nilai profit yang maksimal (Cari dengan kriteria greedy dan algoritma greedy).

Jawab :

N = 4

M = 30 kg

W1,W2,W3,W4 = 20 kg,18 kg,15 kg,10 kg

P1,P2,P3,P4 = 25,20,15,9

A . Cara Kriteria Greedy Profit terbesar

X1,X2,X3,X4 = 1,5/9,0,0

Pembatas = (20.1)+(18.5/9)+0+0 = 20+10 = 30

Fungsi tujuan = (25.1)+(20.5/9)+0+0 = 25 + 11,1 = 36,1

B . Cara Kriteria Greedy bobot terkecil

X1,X2,X3,X4 = 1,1,5/8,0

Pembatas = (10.1) + (15.1)+(18.5/8)+0 = 10+15+5+0 = 30

Fungsi tujuan = (9.1)+(15.1)+(20.5/18)+0 = 9+15+5,6+0 = 29,6

C. (P1,P2,P3) = 25,20,15,9
(M1,M2,M3) = 20kg,18kg,15kg,10kg

P1/W1 = 1,25
P2/W2 = 1,11
P3/W3 = 1
P4/W4 = 0,9

Dari 4 kriteria di atas dapat disimpulkan bahwa fungsi tujuan yang bernilai maximum adalah 36,1 dengan fungsi pembatasnya adalah 30 dan nilai probabilitasnya adalah (X1, X2, X3,X4) = (1, 5/9,0, 0), jadi disini yang memeberikan hasil optimal pada kriteria yang ke-3 yaitu Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)