METODE GREEDY MASALAH KNAPSACK Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat maksimum M dan sehimpunan benda A = {a0,a1,...,an-1} yang berbobot W = {w0,w1,...,wn-1}. Setiap benda tersebut diberikan nilai profit yang dinotasikan dengan P = {p0,p1,...,pn-1}. Jika kita diperbolehkan memasukkan zi bagian dari benda ai yang ada ke dalam knapsack dimana 0 ≤zi ≤ 1 , maka kita dapatkan profit sebesar zi pi untuk benda ai tersebut.
Yang dimaksud dengan masalah knapsack adalah : Bagaimana kita memilih atau menentukan zi untuk masing-masing benda ai dari keadaan di atas dengan tujuan mendapatkan total profit yang maksimal, dan dengan kendala bahwa total bobot dari benda-benda yang dimasukkan ke dalam knapsack tidak melebihi M.
Secara matematis, masalah knapsack tersebut dapat ditulis sebagai berikut : maksimumkan Q =
n-1
∑z p i
i
i
≤W
i=0
n −1
dengan kendala
∑z w i
i =0
dan 0 ≤ zi ≤ 1 , pi 〉 0 , wi 〉 0 , 0 ≤ i ≤ n-1
Sebuah solusi yang optimal adalah himpunan Z = {z0,z1,...,zn-1} yang memaksimalkan nilai Q dan memenuhi kendala-kendala yang ada.
Contoh : 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
Metode Greedy 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 !
Algoritma Sekuensial Knapsack Metode Greedy Salah satu cara untuk menyelesaikan masalah knapsack secara sekuensial adalah dengan pemakaian metode Greedy. Procedure tersebut disebut procedure GREEDY_KNAPSACK. Sebelum procedure tersebut digunakan, benda-benda harus diurutkan rasio pi/wi -nya tidak menaik. Dengan kata lain : p0/ w0 ≥ p1 / w1 ≥ ... ≥ pn-1 / wn-1 Adapun procedure GREEDY_KNAPSACK adalah sebagai berikut : procedure GREEDY_KNAPSACK(P,W,M,Z,n) real P(0:n-1),W(0:n-1),Z(0:n-1),cu;
{n = banyak benda}
integer i,n; Z←0
{ Z(0), Z(1), . . . , Z(n-1) = 0}
cu ← M for i ← 0 to n-1 do if W(i) 〉 cu then exit endif Z(i) ← 1 cu ← cu - W(i) repeat if i ≤ n-1 then Z(i) ← cu/W(i) endif end GREEDY_KNAPSACK
Jika algoritma ini digunakan untuk menyelesaikan masalah seperti pada contoh yang lalu, dimana n = 4; M = 15; W = { 5,9,2,4 }; P = { 100,135,26,20 }, maka akan terlihat hasil tracenya sebagai berikut : Z←0 cu ← 15 i=0 karena W(0) 〈 cu
yaitu : 5 〈 15
berarti :
Logika dan Algoritma – Yuni Dwi Astuti, ST
Z(0) ← 1
2
Metode Greedy 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 Karena 2 ≤ 3
yaitu : 2 〉 1
berarti :
keluar dari loop (exit)
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
Analisis : Kompleksitas waktu dari algoritma Greedy_Knapsack ini adalah O(n). Tetapi jika data yang digunakan belum terurut rasio pi/wi -nya tidak menaik, maka diperlukan kompleksitas waktu sebesar O(n log n) untuk mengurutkan sebelumnya. Sehingga untuk masalah optimisasi knapsack, kompleksitas waktu dari algoritma ini akan lebih besar pada waktu proses pengurutannya.
Latihan : Diketahui 3 buah benda dan sebuah knapsack dengan kapasitas maksimum 20. Berat dan profit dari masing-masing benda tersebut adalah (18, 15, 10) dan (25, 24, 15). Tentukanlah Z agar diperoleh total profit yang maksimal ! Jawab : Pertama, kita periksa apakah rasio pi/wi -nya tidak menaik. p0/w0 = 25/18 p1/w1 = 24/15 p2/w2 = 15/10
Logika dan Algoritma – Yuni Dwi Astuti, ST
3
Metode Greedy Terlihat bahwa syarat rasio pi/wi -nya tidak menaik belum terpenuhi. Jadi susunan (urutan) -nya untuk sementara kita ubah, agar syarat rasio pi/wi -nya tidak menaik terpenuhi dan kita dapat menyelesaikan masalah tersebut dengan procedure GREEDY_KNAPSACK. Untuk itu, kita ubah sementara urutan benda-bendanya (setelah diperoleh jawaban sementara, kita kembalikan urutan ke susunan semula). Perubahan yang kita lakukan adalah sebagai berikut : urutan ke-
urutan ke-
(yang lama) (yang baru) 0
2
1
0
2
1
sehingga syaratnya terpenuhi ; 24/15 〉 15/10 〉 25/18 → rasio pi/wi -nya tidak menaik Sekarang kita sudah dapat menggunakan procedure GREEDY_KNAPSACK untuk menyelesaikan masalah tersebut. Adapun hasil trace-nya adalah sebagai berikut : Z←0 cu ← 20 i=0 karena W(0) 〈 cu
yaitu : 15 〈 20 berarti :
Z(0) ← 1 cu ← 20 - 15 = 5
i=1 karena W(2) 〉 cu Karena 1 ≤ 2
yaitu : 10 〉 5
berarti :
keluar dari loop (exit)
maka Z(1) ← cu/W(1) = 5/10 = 0,5
Jadi diperoleh : Z(0) = 1 ; Z(1) = 0,5 ; Z(2) = 0 Sekarang urutannya kita kembalikan seperti semula, yakni :
Logika dan Algoritma – Yuni Dwi Astuti, ST
4
Metode Greedy urutan ke-
urutan ke-
Z(i)
(yang saat ini) (yang semula) 2
0
0
0
1
1
1
2
0,5
Jadi optimisasi masalah knapsack diperoleh bila Z = { 0; 1; 0,5 } Sehingga Q
= 0 x 25 + 1 x 24 + 0,5 x 15 = 0 + 24 + 7,5 = 31,5
MASALAH POHON RENTANGAN MINIMAL Permasalahan umum dari pohon rentangan minimal adalah mencari minimum biaya (cost) pohon rentangan dari setiap ruas suatu graf yang membentuk pohon. Setiap graf tidak dapat ditentukan pohon rentangan minimalnya. Adapun graf yang dapat kita tentukan pohon rentangan minimalnya adalah graf yang memenuhi ketiga syarat berikut : 1. graf tersebut harus terhubung 2. setiap ruas dari graf tersebut harus mempunyai nilai atau bobot (graf berlabel) 3. graf teresbut tidak berarah Algoritma yang dapat digunakan untuk menyelesaikan masalah pohon rentangan minimal cukup banyak. Dalam pembahasan ini, algoritma yang akan dipakai adalah algoritma PRIM’S. Berikut ini akan disajikan langkah-langkah penyelesaian masalah pohon rentangan minimal dengan menggunakan algoritma PRIM’S.
PROCEDURE PRIM(E,COST,n,T,mincost) REAL COST(n,n),mincost INTEGER NEAR(n),n,i,j,k,l,T(1:n-1,2) (k,l) ← ruas dengan biaya atau bobot yang minimum mincost ← COST(k,l)
Logika dan Algoritma – Yuni Dwi Astuti, ST
5
Metode Greedy (T(1,1),T(1,2)) ← (k,l) FOR i ← 1 TO n DO IF COST (i,l) < COST(i,k) THEN NEAR (i) ←l ELSE NEAR(i) ← k ENDIF REPEAT i NEAR(k) ← NEAR(l) ← 0 FOR i ← 2 TO n-1 DO Pilih j (sebuah index) sedemikian sehingga NEAR(j) ≠ 0 AND COST(j,NEAR(j)) adalah minimum (T(i,1),T(i,2)) ← (j,NEAR(j)) mincost ← mincost + COST(j,NEAR(j)) NEAR(j) ← 0 FOR k ← 1 TO n DO IF NEAR(k) ≠ 0 AND COST(k,NEAR(k)) > COST(k,j) THEN NEAR(k) ← j ENDIF REPEAT k REPEAT i IF mincost ≥ ~ THEN PRINT ‘bukan pohon rentangan’ ENDIF END PRIM
Contoh : Perhatikan graf berikut ini :
Tentukanlah nilai pohon rentangan minimalnya, serta pohon yang membentuk pohon rentangan minimal tersebut.
Logika dan Algoritma – Yuni Dwi Astuti, ST
6
Metode Greedy Penyelesaian : Dengan menggunakan algoritma PRIM’S, prosesnya adalah sebagai berikut : (k,l) ← (1,2) mincost ← COST(1,2) = 10 (T(1,1),T(1,2)) ← (1,2) i=1 COST (1,2) < COST(1,1) … ? 10 < ~ … → TRUE : NEAR (1) ←2 i=2 COST (2,2) < COST(2,1) … ? ~ < 10 … → FALSE : NEAR (2) ←1 i=3 COST (3,2) < COST(3,1) … ? 50 < ~ … → TRUE : NEAR (3) ←2 i=4 COST (4,2) < COST(4,1) … ? ~ < 30 … → FALSE : NEAR (4) ←1 i=5 COST (5,2) < COST(5,1) … ? 40 < 45 … → TRUE : NEAR (5) ←2 i=6 COST (6,2) < COST(6,1) … ? 25 < ~ … → TRUE : NEAR (6) ←2 NEAR(1) ← NEAR(2) ← 0
i=2 Pilih j = 6 karena NEAR(6) ≠ 0 dan COST(6,NEAR(6)) adalah minimum (T(2,1),T(2,2)) ← (6,2) mincost ← 10 + COST(6,2) = 10 + 25 = 35 NEAR(6) ← 0
Logika dan Algoritma – Yuni Dwi Astuti, ST
7
Metode Greedy k=1 NEAR(1) ≠ 0 dan COST(1,NEAR(1)) > COST(1,6) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=2 NEAR(2) ≠ 0 dan COST(2,NEAR(2)) > COST(2,6) … ? 0 ≠ 0 dan ~ > 25 … → FALSE dan TRUE → FALSE k=3 NEAR(3) ≠ 0 dan COST(3,NEAR(3)) > COST(3,6) … ? 2 ≠ 0 dan 50 > 15 … → TRUE dan TRUE → TRUE : NEAR(3) = 6 k=4 NEAR(4) ≠ 0 dan COST(4,NEAR(4)) > COST(4,6) … ? 1 ≠ 0 dan 30 > 20 … → TRUE dan TRUE → TRUE : NEAR(4) = 6 k=5 NEAR(5) ≠ 0 dan COST(5,NEAR(5)) > COST(5,6) … ? 2 ≠ 0 dan 40 > 55 … → TRUE dan FALSE → FALSE k=6 NEAR(6) ≠ 0 dan COST(6,NEAR(6)) > COST(6,6) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE
i=3 Pilih j = 3 karena NEAR(3) ≠ 0 dan COST(3,NEAR(3)) adalah minimum (T(3,1),T(3,2)) ← (3,6) mincost ← 35 + COST(3,6) = 35 + 15 = 50 NEAR(3) ← 0 k=1 NEAR(1) ≠ 0 dan COST(1,NEAR(1)) > COST(1,3) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=2 NEAR(2) ≠ 0 dan COST(2,NEAR(2)) > COST(2,3) … ? 0 ≠ 0 dan ~ > 50 … → FALSE dan TRUE → FALSE k=3
Logika dan Algoritma – Yuni Dwi Astuti, ST
8
Metode Greedy NEAR(3) ≠ 0 dan COST(3,NEAR(3)) > COST(3,3) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=4 NEAR(4) ≠ 0 dan COST(4,NEAR(4)) > COST(4,3) … ? 6 ≠ 0 dan 20 > ~ … → TRUE dan FALSE → FALSE k=5 NEAR(5) ≠ 0 dan COST(5,NEAR(5)) > COST(5,3) … ? 2 ≠ 0 dan 40 > 35 … → TRUE dan TRUE → TRUE : NEAR(5) = 3 k=6 NEAR(6) ≠ 0 dan COST(6,NEAR(6)) > COST(6,3) … ? 0 ≠ 0 dan ~ > 15 … → FALSE dan TRUE → FALSE
i=4 Pilih j = 4 karena NEAR(4) ≠ 0 dan COST(4,NEAR(4)) adalah minimum (T(4,1),T(4,2)) ← (4,6) mincost ← 50 + COST(4,6) = 50 + 20 = 70 NEAR(4) ← 0 k=1 NEAR(1) ≠ 0 dan COST(1,NEAR(1)) > COST(1,4) … ? 0 ≠ 0 dan ~ > 30 … → FALSE dan TRUE → FALSE k=2 NEAR(2) ≠ 0 dan COST(2,NEAR(2)) > COST(2,4) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=3 NEAR(3) ≠ 0 dan COST(3,NEAR(3)) > COST(3,4) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=4 NEAR(4) ≠ 0 dan COST(4,NEAR(4)) > COST(4,4) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=5 NEAR(5) ≠ 0 dan COST(5,NEAR(5)) > COST(5,4) … ?
Logika dan Algoritma – Yuni Dwi Astuti, ST
9
Metode Greedy 3 ≠ 0 dan 35 > ~ … → TRUE dan FALSE → FALSE k=6 NEAR(6) ≠ 0 dan COST(6,NEAR(6)) > COST(6,4) … ? 0 ≠ 0 dan ~ > 20 … → FALSE dan TRUE → FALSE
i=5 Pilih j = 5 karena NEAR(5) ≠ 0 dan COST(5,NEAR(5)) adalah minimum (T(5,1),T(5,2)) ← (5,3) mincost ← 70 + COST(5,3) = 70 + 35 = 105 NEAR(5) ← 0 k=1 NEAR(1) ≠ 0 dan COST(1,NEAR(1)) > COST(1,5) … ? 0 ≠ 0 dan ~ > 45 … → FALSE dan TRUE → FALSE k=2 NEAR(2) ≠ 0 dan COST(2,NEAR(2)) > COST(2,5) … ? 0 ≠ 0 dan ~ > 40 … → FALSE dan TRUE → FALSE k=3 NEAR(3) ≠ 0 dan COST(3,NEAR(3)) > COST(3,5) … ? 0 ≠ 0 dan ~ > 35 … → FALSE dan TRUE → FALSE k=4 NEAR(4) ≠ 0 dan COST(4,NEAR(4)) > COST(4,5) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=5 NEAR(5) ≠ 0 dan COST(5,NEAR(5)) > COST(5,5) … ? 0 ≠ 0 dan ~ > ~ … → FALSE dan FALSE → FALSE k=6 NEAR(6) ≠ 0 dan COST(6,NEAR(6)) > COST(6,5) … ? 0 ≠ 0 dan ~ > 55 … → FALSE dan TRUE → FALSE mincost ≥ ~ … ? 105 ≥ ~ … → FALSE
Logika dan Algoritma – Yuni Dwi Astuti, ST
10
Metode Greedy
∴ terdapat sebuah pohon rentangan, yang mempunyai nilai minimal = 105 Berikut adalah bentuk pohon rentangan minimalnya :
Logika dan Algoritma – Yuni Dwi Astuti, ST
11
