Pemecahan Soal Dengan Metode Greedy

soal & penyelesaian menggunakan metode greedy

                kali ini saya akan mencoba untuk menjelaskan pemecahan soal dengan metode greedy, dimana kali ini saya akan memcebri contoh sebagai berikut.

Pertama Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat maksimum 15 Kg dan sehimpunan benda A = {a0, a1, a2, a3} yang berbobot (dalam Kg) W = {5,9,2,4}. Setiap benda tersebut diberikan nilai profit P = {100, 135, 26, 20}. Jika kita diperbolehkan memasukkan zi  

bagian dari benda ai yang ada ke dalam knapsack dimana 0 ≤ zi ≤ 1 , maka tentukanlah Z = {z0,z1,z2,z3} agar diperoleh total profit yang maksimal !

Jawab :

dik : n = 4; M = 15;

        W = { 5,9,2,4 };

        P = { 100,135,26,20 },

 dit : total profit yang maksimal ?

Barang ke -	Berat(Wi)	Keuntungan(Pi)	Pi/Wi
Z0	5	100	20
Z1	9	135	15
Z2	2	26	13
Z3	4	20	5

Z ← 0

cu ← 15

i = 0

karena W(0) 〈 cu yaitu : 5 〈 15 berarti : Z(0) ← 1

cu ← 15 - 5 = 10

i = 1

karena W(1) 〈 cu yaitu : 9 〈 10 berarti : Z(1) ← 1

cu ← 10 - 9 = 1

i = 2

karena W(2) 〉 cu yaitu : 2 〉 1 berarti : keluar dari loop (exit)

Karena 2 ≤ 3 maka Z(2) ← cu/W(2) = 1/2 = 0,5

Jadi optimisasi masalah knapsack diperoleh bila Z = { 1; 1; 0,5; 0 }

Sehingga Q = 1 x 100 + 1 x 135 + 0,5 x 26 + 0 x 20

= 100 + 135 + 13 + 0

= 248

Sumber : google.com