Contoh Soal dan Penyelesaian Dengan Metode Greedy

1. Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat maksimum 15 Kg dan sehimpunan benda A = {a₀, a₁, a₂, a₃} 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 !

Penelesaian :

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

2. Misal terdapat 3 buah prg.(n=3) yg masing-masing mempunyai panjang persegi.

(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, yg didapat dari 

nilai faktorial 3 --> 3! (ingat faktorial n!).

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

Dari tabel tersebut, didapat Susunan / order yg optimal adalah :

susunan pertama untuk program ke tiga = 3

susunan kedua untuk program kesatu = 5

susunan ketiga untuk program kedua = 10