Metode Greedy
8:15 PMAudya Elita Putri 51414801 1IA24
Metode
ini digunakan untuk memperoleh solusi yang optimal dari suatu masalah yang
mempunyai 2 indikator yaitu: adanya fungsi tujuan & pembatas (Constrain).
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:
1. https://kevinkarundeng.wordpress.com/2012/11/05/contoh-soal-algoritma-greedy-dan-knapsack-problem/
2. http://caeyoooo90.blogspot.com/2011/04/soal-penyelesaian-menggunakan-metode.html
0 comments