Metode Greedy

Kali ini Kuliah Struktur data dan Algoritma Semester 3 Fakultas Teknik Jurusan Teknik Informatika UIKA Bogor.

Materinya Tentang Metode Greedy.

yup Greedy artinya dalam bahasa Inggrisnya Rakus.

hoho,.

nah karena data itu rakus (banyak) bagaimana carana data itu disimpan secara optimal.

cekidot.

Metode greedy :

1. Optimal on Tape stronge problem

2. Knapsack Problem

3. Minimum Spanning tree Problem

4. Shortest path problem

1. Optimal on tare storage

Menentukan urutan penyimpanan yang menghasilkan solusi optimal.

- Diurutkan secara sequential

L1 = 5 ; L2=10 ; L3=3

Bagaimana penysunan dalam menyimpan data pada storage dengan optimal

2. Metode Knapsack

Dapat Diselesaikan dengan 3 cara

a.  Secara Matematika

b.  Menggunakan Kriteria Greedy

c.  Menggunakan algoritma pemrograman greedy

Optimal on Tape stronge problem :

L1=5 ; L2=10  ; L3=3 

Karena datanya ada 3

jadi 3! (baca : tiga faktorial)

3! = 6

jadi ada 6 kemungkinan :

I.    123

II.   132

III.  213

IV.  231

V.   312

VI.  321

Perhitungan secara matematikanya :

I   = 5 + (5+10) +  (5+10) + 3 = 38

II  = 5 + (5+3) + (5+3)+10 = 31

III = 10 + (10+5) +(10+5) + 3 = 43

IV = 10 + (10+3) + (10+3) +5 =  41

V  = 3 + (3+5) + (3+5)+10 = 29    

VI = 3+(3+10)+(3+10)+5 = 34

2. Knapsack Problem

M = 20 Kg

w1 = 18  :  p1 = 25

w2 = 15  ;  p2 = 24

w3 = 10  ;  p3 = 15

Sigma w1 . x1 < M
w1 . x1 + w2 . x2 + w3 . x3 < M
18 . 1  + 15 . ?  + 10 . 0  < 20
18 + 15x < 20
15x < 2
x < 2/15

2. Menggunakan Greedy (3)
    1. wi min
    2. pi min
    3. pi/wi max

Bersambung.......
^-^