Logika Dan Agoritma

METODE GREEDY

Disusun oleh:
- Nasrul Fatikhin

- Hutama Bagus Reynaldy

- Fitria Tis'a Tiffani

A. PENGERTIAN 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.

B. PROSES KERJA METODE GREEDY

 Menyelesaikan suatu masalah yang terdiri dari beberapa fungsi pembatas dan satu fungsi tujuan, dengan cara memilih beberapa solusi yang memungkinkan (Feasible Solution/ Feasible Sets), yaitu apabila solusi telah memenuhi fungsi tujuan/ obyektif.

Metode Greedy dapat di gunakan dalam penyelesaian masalah-masalah sebagai berukut :

1. Optimal On Tape Storage Problem

2. Knapsack Problem

3. Minimum Spanning Tree Problem

4. Shortest Path Problem

I. Optimal On Tape Storage Problem

 Adalah bagaimana cara mengoptimalkan penyimpanan, agar data yang tersimpan dapat termuat dengan optimal.

Misal

Terdapat n program yang akan di simpan dalam pita (tape). Pita tersebut mempunyai panjang maksimal sebesat L, masing-masing program yang akan disimpan memiliki panjang L1,L2,L3,.....Ln. Cara penyimpanannya adalah dengan cara penyimpanan secaea tersusun (Sequential). 

Contoh :

Terdapat 3 program. Masing-masing program memiliki panjang 5, 10 dan 3. Tentukan urutan penyimpanannya secara berurutan (Sequential) agar optimal.

Diketahui :

n = 3

L1 = 5

L2 = 10

L3 =   3

ORDERING	D (L)
1, 2, 3	5 + (5 + 10) + (5 + 10 + 3) = 38
1, 3, 2	5 + (5 + 3) + (5  + 3 +10) = 31
2, 1, 3	10 + (10 + 5) + (10 + 5 + 3) = 43
2, 3, 1	10 + (10 + 3) + (10 + 3 + 5) = 41
3, 1, 2	3 + (3 + 5) + (3 + 5 + 10) = 29
3, 2, 1	3 + (3 + 10) + (3 + 10 + 5) = 34

Dari Tabel tersebut, didapat susunan/order yang optimal, yaitu :

Program ke 3 sebagai susunan ke 1

Program ke 1 sebagai susunan ke 2

Program ke 2 sebagai susunan ke 3

b. Knapsack Problem

 Adalah bagaimana menentukan pemilihan barang dari sekumpualan barang dimana setiap barang tersebut  memiliki berat dan profit masing-masing, sehingga didapat pemilihan barang dengan profit yang maksimum.

Ø  Penyelesaian Knapsack dengan Kriteria Greedy 

Konsep dr kriteria yg ditawarkan oleh metode Greedy yaitu :

1.        Pilih obyek (barang) dengan nilai Pi maximal atau terbesar

2.        Pilih obyek (barang) dengan berat Wi minimal dahulu.

3.        Pilih obyek (barang) dgn perbandingan nilai & berat yaitu Pi/Wi yang terbesa.  

Contoh :

Diketahui bahwa kapasitas M = 20kg ,Dengan jumlah barang n=3 ,Berat Wi masing-masing barang (1, W2, W3) = (18, 15, 10),Nilai Pi masing-masing barang (P1, P2, P3) = (25, 24, 15).

Pilih barang dengan Nilai Profit Maksimal

P1 = 25       X1 = 1, dimisalkan sebagai batas atas nilai

P2 = 24       X2 = 2/15, dihitung dengan Fungsi Pembatas

P3 = 15       X3 = 0, dimisalkan sebagai batas bawah nilai

Pilih barang dengan Berat Minimal 

W1 = 18 

X1 = 0, sebagai batas bawah 

W2 = 15 

X2 = 2/3,dihitung dgn Fungsi Pembatas 

W3 = 10 

X3 = 1, sebagai batas atas 

Pilih barang dgn menghitung perbandingan yg terbesar dr Profit dibagi Berat (Pi/Wi) yg diurut secara tidak naik, yaitu : 

P1/W1 = 25/18 karena terkecil maka X1 = 0 

P2/W2 = 24/15 karena terbesar maka X2 = 1 

P3/W3 = 15/10 dengan Fungsi pembatas X3 = 1/2

Dibuatkan tabel berdasarkan elemen dari ke-3 kriteria metode Greedy

Solusi Ke	(X1,X2,X3)	∑WiXi	∑PiXi
PiMax	(1, 2/15, 0)	20	28,2
WiMin	0, 2/3, 1	20	31,0
Pi/Wi Max	0, 1, 1/2	20	31.5

Nilai profit maksimal = 31.5 dengan komposisi yang sama