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 :

Metode Greedy 1

Metode Greedy 2

Divide and Conquer

Hal yang Membuat Resah dan Solusinya

Sekitar setahun lalu, saya mengalami beberapa hal yang mungkin membuat saya resah. Setahun yang lalu, saya mengalami beberapa yang saya anggap adalah sebuah kegagalan dalam hidup saya serta dalam meraih cita-cita saya.

Dimulai dari saat saya duduk dibangku kelas 3 SMA semester 2, saat hari-hari mendekati UN dan banyak ujian serta try out yang menghadang. Saya dihadapkan oleh beberapa masalah, saya harus mengalami kegagalan saya dalam mencapai tujuan saya yaitu lolos perguruan tinggi negri melalui jalur SNMPTN atau banyak yang menyebutnya PMDK (jalur rapot). Saya merasa, saya sudah sangat maksimal dalam mendapatkan nilai-nilai pada raport tersebut. Namun, saya gagal untuk yang pertama kalinya dan mungkin bukan rejeki saya dalam mendapatkan perguruan tinggi negri melalui jalur tersebut. Disitu saya merasa sangat kecewa dengan diri saya, karena saya sudah mengecewakan orang tua saya yang sudah sangat berharap pada hasil tersebut.

Beberapa hari kemudian, saya mencoba bangkit dan mendaftar lagi dengan jalur tulis atau SBMPTN. Saya berusaha belajar semaksimal mungkin untuk meraih apa yang saya inginkan. Hampir setiap hari saya datang ke tempat bimbel untuk mempelajari tipe-tipe soal yang biasa keluar pada ujian tersebut. Hal tersebut saya lakukan hingga hari ujian tiba. Namun hasilnya, saya kembali gagal. Saya makin kecewa dengan hasil yang saya dapatkan.

Saya mencoba bangkit lagi dengan mengikuti beberapa ujian mandiri yang diselenggarakan oleh pihak universitas dalam penerimaan mahasiswa baru. Tetapi, dengan hasil yang sudah saya dapatkan sebelumnya, semangat saya mulai pudar. Bukannya makin rajin belajar, saya malah makin banyak santai dan kurang mempersiapkan diri untuk menghadapi ujian mandiri tersebut. Hasilnya, saya gagal dalam banyak ujian mandiri yang saya ikuti

Kecewa, sangat kecewa terlebih melihan uang dan tenaga yang sudah orang tua saya keluarkan demi untuk mengikuti ujian-ujian tersebut. Saat itu saya merasa itu merupakan kegagalan terparah yang pernah saya alami.

Sampai hasil ujian terakhir saya dinyatakan gagal, saya mencoba bangkit dengan mendaftar pada beberapa universitas swasta. Kakak saya merekomendasikan Gunadarma sebagai pilihan, karena ia merupakan alumni Universitas Gunadarma yang terkenal dengan lulusan ITnya yang bagus.

SOLUSI :

Dari hal-hal yang saya alami, saya sadar bahwa saya tidak harus terpatok pada pilihan saya. Dan saya mungkin masih kurang maksimal dalam usaha saya mendapatkan apa yang saya inginkan. Namun, masih banyak hal yang dapat membantu saya untuk membanggakan kedua orang tua saya. Saya sempat berfikir bahwa Tuhan tidak adil, kemudian saya tau bahwa inilah jalan Tuhan yang terbaik untuk saya. Saya belum siap untuk hidup mandiri merantau di luar kota serta masih banyak yang harus saya lakukan untuk menyelesaikan tugas saya sebagai anggota organisasi disini.

Saya mencoba untuk selalu berfikir positif bahwa semua yang terjadi ini adalah karena kehendakNya dan usaha yang sudah kita lakukan. Belajar, berdoa, dan selalu berusaha, itulah yang akan dan masih sedang saya lakukan untuk mengatasi semuanya. Semua itu terbukti dengan apa yang saya alami saat ini. Hati saya sudah tenang dan lebih memikirkan yang terbaik kedepannya, bukannya terpuruk dalam masa lalu

Saya mencoba bangkit serta semangat dalam belajar, hasilnya pun saya mendapatkan nilai pada semester 1 yang cukup memuaskan serta dapat membuat kedua orang tua saya tersenyum. Dan belajar untuk siap hidup lebih mandiri. Semoga seterusnya saya makin terus membanggakan kedua orang tua saya, dan apa yang sudah saya perjuangkan mendapatkan hasil yang baik dan terbaik

Sumber Gambar 1

Sumber Gambar 2