Algorima Greedy

ALGORITMA GREEDY

CONTOH SOAL SISTEM PENJADWALAN

Lima pelanggan dengan

t1 = 5,              t2 = 2,              t3 = 4,              t4 = 3,              t5 = 6 

Enam urutan pelayanan yang mungkin:

Urutan                                     T

1, 2, 3,4,5 :      5 + (5 + 2) + (5 + 2 + 4 ) + (5 + 2 + 4 + 3) + (5 + 2 + 4 + 3 + 6)= 57

1, 2, 3,5,4 :      5 + (5 + 2) + (5 + 2 + 4 ) + (5 + 2 + 4 + 6) + (5 + 2 + 4 + 6 + 3)= 60

1, 2, 4,5,3 :      5 + (5 + 2) + (5 + 2 + 3 ) + (5 + 2 + 3 + 6) + (5 + 2 + 3 + 6 + 4)= 58

1, 3, 2,4,5 :      5 + (5 + 4) + (5 + 4 + 2 ) + (5 + 4 + 2 + 3) + (5 + 4 + 2 + 3 + 6)= 59

2, 1, 3,4,5 :      2 + (2 + 5) + (2 + 5 + 4 ) + (2 + 5 + 4 + 3) + (2 + 5 + 4 + 3 + 6)= 54

2, 1, 4,3,5 :      2 + (2 + 5) + (2 + 5 + 3 ) + (2 + 5 + 3 + 4) + (2 + 5 + 3 + 4 + 6)= 53

2, 3, 4,1,5 :      2 + (2 + 4) + (2 + 4 + 3 ) + (2 + 4 + 3 + 5) + (2 + 4 + 3 + 5 + 6)= 51

2, 4, 3,1,5 :      2 + (2 + 3) + (2 + 3 + 4 ) + (2 + 3 + 4 + 5) + (2 + 3 + 4 + 5 + 6)= 50 (OPTIMAL)

CONTOH SOAL PERMASALAHAN KNAPSACK

w1 = 9;   p1 = 45;       w2 = 3;    p2 = 9;

w3 = 7;  p3 = 14;        w4 = 2;    p4= 4;

knapsack K = 15

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi / wi	profit	weight	density
1	9	45	5	1	0	1	1
2	3	9	3	1	1	1	1
3	7	14	2	0	1	0	0
4	4	8	2	0	1	0	0
Total bobot				12	14	12	12
Total keuntungan				54	31	54	54

Jadi,

Solusi Optimal adalah (1, 1, 0, 0) dengan total bobot 12 dan total keuntungan 54

CONTOH SOAL 2

w1 = 50;   p1 = 20;     w2 = 25;    p2 = 18;

w3 = 24;  p3 = 15;      w4 = 15;    p4= 8;

w5 = 5;    p4= 5;

knapsack K = 50

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi / wi	profit	weight	density
1	50	20	0,4	1	0	0	0
2	25	18	0,7	0	0	1	1
3	24	15	0,6	0	1	0	1
4	15	8	1	0	1	1	0
5	5	5	0,2	0	1	1	0
Total bobot				50	44	45	49
Total keuntungan				20	28	31	33

Solusi optimal (0,1,1,0,0) dengan total bobot 49 total keuntungan 33