Metode Greedy, Divide & Conquer (Algoritma Pemrograman 2C)

Nama  =  Fitri Ayu Anggraini

NPM =  54414313

Kelas  =  1IA24

 

Penyelesaian Soal & Penjelasan

1. Metode Greedy

Metode ini digunakan untuk memperoleh solusi yang optimal dari suatu masalah yang mempunyai 2 indikator yaitu : adanya fungsi tujuan & pembatas (Constrain). Untuk menyeselesaikan suatu permasalahan dengan input data yg terdiri dari beberapa fungsi pembatas & 1 fungsi tujuan yg diselesaikan dengan memilih beberapa solusi yg mungkin (feasible solution/feasible sets), yaitu bila telah memenuhi fungsi tujuan/obyektif.
 

Contoh kasus : Tersedia uang senilai Rp 1.000, Rp 5.000 dan Rp. 10.000, seseorang hendak memecahkan uang sebesar Rp 18.000. Solusi yang diperoleh bisa didaptkan dengan berbagai cara, contohnya beberapa cara seperti dibawah ini :

• 1.000 x 18 = 18.000                                                [18 lembar]
• ( 5.000 x 2 ) + ( 1.000 x 8 ) = 18.000                      [10 lembar]
• ( 5.000 x 3 ) + ( 1.000 x 3 ) = 18.000                      [ 6 lembar]
• ( 10.000 ) + ( 1.000 x 8 ) = 18.000                          [ 9 lembar]
• ( 10.000 ) + 5.000 + ( 1.000 x 3 ) = 18.000             [ 5 lembar]

Pada setiap langkah, pilih lembaran dengan nilai sebesar mungkin dari himpunan lembaran yang tersisa dengan syarat tidak melebihi nilai uang yang ingin ditukarkan agar lembaran yang ditukarkan menjadi sedikit. Maka solusi optimal dari kasus penukaran uang lembaran di atas adalah 5 lembar.

2. Divide & Conquer

Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

• Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
• Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
• Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah. 

Contoh : Diberikan tabel APC yang sudah berisi 8 nilai dengan tipe data integer. Carilah nilai minimum dan nilai maksimum sekaligus di dalam tabel tersebut.

Ukuran tabel hasil pembagian/dibagi (DIVIDE) dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah.

Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen dari setiap bagian. (CONQUER)

Lalu, setelah mendapat hasil dari setiap bagian dikombinasikan (COMBINE) antara bagian satu dan dua. Maka akan diperoleh hasil dari minimal dan maksimalnya.

 

Source : http://bloggdimas.blogspot.com , http://gunadarma.academia.edu/NiaMoraa ,  http://suhandono.staff.gunadarma.ac.id