Jln. Abdul Rahman Saleh No.18. Telp (0561) 583924

BINA SARANA INFORMATIKApontianak

“LOGIKA & ALGORITMA”

KELOMPOK 4

METODE GREEDY

Nama Dosen : Rabiatul Adwiya, S.KomKelas : 12.1B.30Nama Anggota : - Dedi Kurniadi (12133204) - Fakhrul Reza (12133316)

- Fasabrur Jamil (12133442) - Irwan Hendra Saputra (12133463) - Mentariana (12133484) - Andri Tentoni (12133519) - Agung Tri W (12133521) - Erik (12133522) - Yaldi Apiansyah (12133524)

- Doni Wiratmoko (12133537)

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.

METODE GREEDY

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

PENGERTIAN GREEDY

Untuk menyeselesaikan suatu permasalahan dengan n input data yang terdiri dari beberapa fungsi pembatas & 1 fungsi tujuan yang diselesaikan dengan memilih beberapa solusi yang mungkin (feasible solution / feasible sets), yaitu bila telah memenuhi fungsi tujuan / obyektif.

Proses Kerja Metode Greedy :

1. Optimal On Tape Storage Problem2. Knapsack Problem3. Minimum Spanning Tree Problem4. Shortest Path Problem.

Metode GREEDY digunakan dalam penyelesaianmasalah - masalah :

Permasalahan bagaimana mengoptimalisasi storage / memory dalam komputer agar data yg disimpan dapat termuat dgn optimal.

Misalkan terdapat n program. yg akan disimpan didalam pita (tape).Pita tsb

mempunyai panjang maks. sebesar L, masing 2prg. yg akan disimpan mempunyai

panjang L1,L2,L3...,LnCara penyimpanan adalah penyimpanan

secara terurut (sequential).

1. Optimal Storage On Tapes Problem

Persoalan = Bagaimana susunan penyimpanan Program 2 tersebut sehingga :

L1+ L2+ L3+ ... + Ln= L ? Pemecahannya = jika program.2 tersebut

disimpan dlm Order, misalkan adalah Order I, yaitu : j sama dengan ∑tik maka akan didapat

k=1

Contoh :

Misalnya terdapat 3 buah prg (n=3) yg masing 2 mempunyai panjang prg. (I1,I2,I3) = (5,10,3).

Tentukan urutan penyimpanannya secara berurutan (sequential) agar optimal....!

Penyelesaiannya :Dari 3 program tersebut akan didapat 6 buah kemungkinan order, yang didapat dari nilai faktorial 3 →3! (ingat faktorial n!).

Dari tabel tersebut, didapat Susunan / order

yg optimal, sbb :1. Susunan Pertama Untuk Program Ke Tiga2. Susunan Kedua Untuk Program Kesatu3. Susunan Ketiga Untuk Program Kedua

2. KNAPSACK Problem

Kasus : Terdapat n obyek (Xi;i=1,2,3,....n) yang masing - masing

mempunyai berat (weight)/ Wi & masing - masing memiliki nilai (profit) /

Pi yang berbeda-beda.

METODE GREEDY (lanjutan)

Masalah : Bagaimana obyek-obyek tersebut dimuat /

dimasukan kedalam ransel (knapsack) yg mempunyai kapasitas maks. = M. Sehingga timbul permasalahan sbb:

1. Bagaimana memilih obyek yg akan dimuat dari n obyek yang ada sehingga nilai obyek termuat jumlahnya sesuai dengan kapasitas (≤ M)

2. Jika semua obyek harus dimuat kedalam ransel maka berapa bagian dari setiap obyek yang ada dapat dimuat kedalam ransel sedemikian sehingga nilai kum. maks. & sesuai dengan kapasitas ransel ?

Penyelesaian Knapsack Problem :

1. Dengan Secara Matematika2. Dengan Kriteria Greedy.3. Dengan Algoritma Pemrograman

Greedy.

Fungsi tujuan = fungsi utama/obyektif = fungsi yg mjd penyelesaian permasalahan dgn mendptkan solusi yg optimal.

Solusi dimaksud = menemukan nilai/profit yg maks. utk jml obyek yg dimuat dlm ransel shg sesuai kapasitas.

Penyelesaian Knapsack Dengan Secara Matematika

Fungsi pembatas = fungsi subyektif = fungsi yg

bertujuan untuk memberikan batas maks. dr setiap obyek untuk dapat dimuat dalam ransel sehingga kapasitasnya tdk melebihi dr jumlah maks. daya tampung ransel.

Catatan : karena dengan menggunakan Matematikan sangat sulit dan rumit maka tidak dibahas lebih mendalam.

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 terbesar.

Penyelesaian Dengan Kriteria Greedy.

Diketahui bahwa kapasitas M = 20kg ,

Dengan jumlah barang n=3

Berat Wi masing-masing barang(W1, W2, W3) = (18, 15, 10)

Nilai Pi masing-masing barang (P1, P2, P3) = (25, 24, 15)

Penyelesaiannya : Dengan Kriteria Greedy

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 Minimal

W1 = 18 → X1 = 0, sebagai batas bawahW2 = 15 → X2 = 2/3,dihitung dgn Fungsi

PembatasW3 = 10 → X3 = 1, sebagai batas atas

Pilih barang dengan Nilai Profit Maksimal

P1/W1 = 25/18 → karena terkecil maka X1 = 0P2/W2 = 24/15 → karena terbesar maka X2 = 1P3/W3 = 15/10 → dengan Fungsi pembatas X3

= 1/2.

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

Dibuatkan tabel berdasarkan elemen dari ke-3 kriteria metode Greedy

Nilai profit maksimal = 31.5 dengan komposisi yang sama

Masukkan objek satu per satu kedalam knapsack. Sekali objek dimasukkan kedalam knapsack, objek tersebut tidakbisadikeluarkan lagi.

Terdapat beberapa strategi greedy yang heuristik yang dapat digunakan untuk memilih objek yang akan dimasukkan kedalam knpesack

Penyelesaian dengan algoritma greedy

- Pada setiap langkah, pilih objek yang mempunyai keuntungan terbesar.

- Mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu.

1. Greedy by profit

- Pada setiap langkah, pilih objek yang mempunyai berat teringan.

- Mencoba memaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek kedalam knapsack

2. Greedy by weight.

- Pada setiap langkah, knapsack diisi dengan objek yang mempunyai pi/wi terbesar.

- Mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.

3. Greedy by density.

Algoritma greedy tidak selalu berhasil menemukan solusi optimal untuk masalah 0/1

Knapsack.

Kesimpulan Dari Pembahasan: