Soal dan Penyelesaian dengan Metode Greedy,Divide,dan Conquer

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

Contoh Soal dengan Menggunakan Metode Divide dan Conquer

Misalkan anda mempunyai array  A [1..n]  yang telah berisi n elemen integer  . Elemen mayoritas  di dalam Aadalah elemen yang terdapat pada lebih dari n /2 posisi (jadi, jika n = 6 atau n = 7,elemen mayoritas terdapat pada paling sedikit 4  posisi). Rancanglah algoritma divide and conquer  (tidak dalam  bentuk pseudo-code, tapi dalam bentuk uraian deskriptif) untuk menemukan elemen mayoritas di dalam A (atau menentukan tidak terdapat elemen mayoritas). Jelaskan algoritma anda dengan contoh sebuah array berukuran 8 elemen.Selanjutnya,  perkirakan kompleksitas algoritmanya dalam hubungan rekursif (misalnya T  ( n ) = bT  ( n /  p ) + h ( n )), lalu selesaikan T  (n) tersebut.

Solusi: 1

n = 1, maka elemen tunggal tersebut adalah mayoritasnya sendiri. n > 1, maka bagi arraymenjadi dua bagian (kiri dan kanan) yang masing-masing berukuran sama (n/2). 3. combine. Ada empat kemungkinan kasus:

Kasus 1

: tidak ada mayoritas pada setiap bagian, sehingga array gabungan keduanya tidak memiliki mayoritas.  Return: “no majority”