Tugas Algoritma Pemrograman AP2C

Nama : Median Syah Putra
Kelas : 1IA25
NPM  : 56414517

Metode Greedy

Metode greedy adalah metode yang digunakan untuk memecahkan persoalan optimasi. Ada 2 macam persoalan optimasi, yaitu maksimasi dan minimasi, artinya dengan metode greedy kita bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang ada.

 Contoh Soal:

Misalkan tersedia koin : 1, 3, 5.

Uang senilai A=8 dapat di tukar dengan cara :
1+1+1+1+1+1+1+1 = 8 (8 koin)
1+1+1+1+1+3=8 (6 koin)
1+1+1+5=8 (4 koin)
1+1+3+3=8 (4 koin)
3+5=8 (2 koin) solusi optimal.

Maka solusi optimal dari kasus penukaran koin di atas adalah 2 koin.

Metode Divide and Conquer

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. 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.

Contoh Soal:

 Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :

   Ukuran table hasil pembagian 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, selanjutnya dikombinaksikan bagian satu dengan yang lain untuk menentukan nilai min dan maks.

Sumber: 

http://kumikochiba.blogspot.com/
http://novatri9.blogspot.com/