LTM Dasar Pemograman Metode Greedy 2

PERTEMUAN 13

METODE GREEDY 2

A.     Pertanyaan

1.    Terdapat sebuah kapal dengan kapasitas 180 Ton, akan memuat  6buah barang masing-masing adalah : Gula Pasir 50 Ton dengan harga 100 Juta,Gula Merah 60 Ton dengan harga 80 Juta, dan Gula Batu 70 Ton dengan harga 90 Juta,Beras 50 Ton dengan harga 150 Juta, Terigu 20 Ton dengan harga 40 Juta,Minyak Goreng 60 Ton dengan harga 200 Juta. Dengan metode algoritma Greedy tentukan barang apa saja yang dimuat truk dengan harga yang paling mahal

2.    Apa yang menjadi persyaratan metode Traveling Salesman, agar perjalanannya efektif dan efisien

3.    Jelaskan manfaat penggunaan Minimum Spanning Tree

4.    Jelaskan manfaat penggunaan Shortest Path Problem

B.     Jawaban

1.     Diketahui M=180

N = 6 buah

(Berat   Wi ) W1 W2 W3 W4  W5 W6          = 50, 60, 70,  50,  20,  60

(Profit  Pi )  P1 P2 P3  P4  P5  P6              = 100, 80, 90, 150 , 40, 200

Gula Pasir         => P1 /W1 => 100/50  = 2        = menjadi urutan 4

Gula Merah       => P2 /W2 =>  80/60   = 1,3     = menjadi urutan 5

Gula Batu          => P3 /W3 =>  90/70  = 1,28    = menjadi urutan 6

Beras                => P4 /W4 => 150/50 = 3         = menjadi urutan 2

Terigu              => P5 /W5 =>  40/20  = 2        = menjadi urutan 3

Minyak goreng  => P6 /W6 => 200/60 = 3,3      = menjadi urutan 1

Menjadi :

(Berat   Wi ) W1 W2 W3 W4  W5 W6    = 60,50,20,50,60,70

(Profit  Pi )  P1 P2 P3  P4  P5  P6           = 200,150,40,100,80,90

2.     Syarat utama yang menjadi persyaratan metode Traveling salesman adalah menentukan WAKTU perjalanan seorang salesman seminimal mungkin.

3.     Manfaat penggunaan Minimum Spanning Tree adalah untuk memilih ruas suatu Graph dengan biaya seminimal mungkin. Kriterianya  :

ü Setiap ruas pada graph harus terhubung (conected)

ü Setiap ruas pada graph harus mempunyai nilai (label graph)

ü Setiap ruas pada graph tidak mempunyai arah (graph tidak berarah)

4.     Manfaat penggunaan Shortest Path Problem adalah untuk menghitung jalur Terpendek dari sebuah graph berarah

ü Kriterianya : - Setiap ruas pada graph harus mempunyai nilai (label graph)

ü Setiap ruas pada graph tidak harus terhubung (unconected)

ü Setiap ruas pada graph harus mempunyai arah (graph berarah)