Contoh Soal Metode Greedy Dan Divide & Conquer Serta Penjelasannya

Contoh Soal Metode Greedy

Jika kita ingin membeli flasdisk dengan harga Rp. 96.000

Uang pecahan yang dipunyai adalah Rp.( 50.000, 20.000, 10.000, 5.000, 2.000, 1.000, )

Metode greedy

Rp .(50.000+20.000+20.000+5.000+1.000) = 5 lembar uang.

Cara lain

RP.(50.000+20.000+10.000+10.000+2.000+2.000+2.000) = 6 lembar uang pecahan

Rp.(20.000+20.000+20.000+20.000+10.000+5.000+1.000) = 7 lembar uang pecahan

Rp.(10.000+10.000+10.000+10.000+10.000+10.000+10.000+10.000+10.000+5.000+1000) = 11 lemar uang pecahan

Penjelasan Metode Greedy diatas

 Strategi Metode Greedy

“Pilihlah uang pecahan dengan nilai pecahan terbesar dari kumpulan pecahan yang ada”

Langkah 1 :

Pilih 1 lembar uang pecahan Rp. 50.000 (Total  = 50.000 = 50.000)

Langkah 2 :

Pilih 2 lembar  uang pecahan Rp. 20.000 (Total = 50.000 + 20.000 + 20.000 = 90.000)

Langkah 3 :

Pilih 1 lembar  uang pecahan Rp. 5.000 (Total = 50.000 + 20.000 + 20.000 + 5.000 = 95.000)

Langkah 4 :

Pilih 1 lembar  uang pecahan Rp 1.000 (Total = 50.000 + 20.000 + 20.000 + 5.000 + 1.000 = 96.000)

Hasil :

Jumlah Pecahan Minimal = 5 Lembar  Uang Pecahan

Contoh Soal Divide & Conquer

Jika kita mempunyai tabel A bernilai =

7

2

5

9

1

3

6

4

Tentukan  urutan dari nilai terkecil ke terbesar ?

Penjelasan Divide & Conquer

Strategi  Divide& Conquar

“pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil”

Langkah 1

pisahkan Tabel menjadi 2, tanpa harus merupah nilai di dalam tabel

Langkah 2

Pisahkan Tabel Menjadi 4, tanpa harus merupah nilai di dalam tabel

Langkah 3

Pisahkan Tabel Menjadi 8, tanpa harus merupah nilai di dalam tabel

Langkah 4

Kembalikan tabel menjadi 4, dengan mengurutkan nilai terkecil sampai nilai terbesar

Langkah 5

Kembalikan Tabel menjadi 2, dengan mengurutkan nilai terkecil sampai nilai terbesar

Langkah 6

Kembalikan Tabel menjadi 1, dengan mengurutkan nilai terkecil sampai nlai terbesar