soal & penyelesaian menggunakan 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 !

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