Soal Metode Greedy dan Divide and Conquer

A.    METODE GREEDY
Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum atau minimum sementara pada setiap langkahnya. Nilai maksimum dan minimum sementara ini dikenal dengan istilah local maximum dan local minimum


Contoh Soal :
Suatu hari, Adi diminta oleh Ibunya untuk membeli 1kg beras ke warung Ibu Neni. Adi membawa uang sebesar Rp 50.000. Setelah sampai di warung, ternyata harga beras tersebut Rp 23.000/kg
Kemudian Adi membayarkan uang tersebut. Namun, Ibu Neni hanya memiliki pecahan uang Rp 1000, Rp 2000, Rp 5000, Rp 10000
Berapa jumlah minumum kemungkinan lembaran uang yang diterima oleh Adi untuk kembalian pembelian tersebut?


Penyelesaian :
Diketahui :
-          Uang Adi = Rp. 50.000
-          Harga Beras = Rp. 23.000/kg
-          Nominal Uang yang dimiliki Ibu Neni
o   Rp. 1000
o   Rp. 2000
o   Rp. 5000
o   Rp. 10.000

Solusi :
1.       Total Kembalian :  50.000 – 23.000 = 27.000
2.       Nominal uang yang dapat dikembalikan
a.       27.000 = 10.000 + 10.000 + 5000 + 2000                                                                    (4 Lembar)
b.      27.000 = 5000 + 5000 + 5000 + 5000 + 5000 + 2000                                               (6 Lembar)
c.       27.000 = 10.000 + 5000 + 5000 + 2000 + 2000 + 2000 + 1000                             (7 Lembar)
d.      27.000 = 10.000 + 10.000 + 2000 + 2000 + 2000 + 1000                                        (6 Lembar)
e.      27.000 = 1000 + 1000 + 1000 + … + 1000                                                   (27 Lembar)
f.        Dst.
3.       Jumlah minimum lembar kembalian : 27.000 = 10.000 + 10.000 + 5000 + 2000      (4 Lembar)
4.       Jumlah maksimum lembar kembalian : 27.000 = 1000 + 1000 + 1000 + … + 1000   (27 Lembar)






B.     DIVIDE AND CONQUER
Divide and Conquer adalah teknik memecah-mecah pekerjaan untuk kemudian dibagikan kepada banyak
Sebuah metode divide and conquer memiliki tiga langkah, yaitu:
Divide (Memecah)
Pada langkah ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
Conquer (Menaklukkan)
Dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
Combine (Menggabungkan)
Setelah menjalankan langkah conquer, tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.

CONTOH :
Dalam sebuah Kapal pengangkut barang terdapat 35 orang awak Kapal. Masing-masing awak tesebut memiliki tugas masing-masing, yaitu sebagai berikut :
-          Ruang Kemudi                  : 5 awak kapal
o   Nahkoda (Kapten Kapal)
o   Komunikator
o   Pengatur dan Pemeriksa Kapal
o   Navigator
o   Pemantau Muatan
-          Logistik Kapal                    : 20 awak
o   Juru Masak
o   Asisten Juru Masak
o   Pengatur Muatan
o   Juru Pompa
o   Kebersihan
-          Mesin Kapal                       : 10 awak
o   Penanggung Jawab
o   Petugas Mesin Induk
o   Petugas Mesin Bantu
o   Petugas Mesin Pompa
o   Juru Listrik
Dengan pembagian tugas dan tanggung tersebut, tentunya sebuah kapal dapat berjalan dengan baik tanpa kesulitan yang berarti



NAMA        : ANDREAS RINANTO
NPM           : 51414134
KELAS       : 1 IA 24

Sumber :