Quiz Algoritma Greedy

Yang dimaksud dengan algoritma greedy adalah …

• Algoritma yang memilih solusi terbaik di setiap langkah berdasarkan informasi lokal untuk mencapai solusi optimal global.

• Algoritma yang mencoba memecahkan masalah dengan memeriksa sebagian kemungkinan solusi.

• Algoritma yang mencoba mencari solusi dengan cara mencoba semua kemungkinan dan memilih solusi terbaik di akhir.

• Algoritma yang menghindari keputusan berdasarkan solusi lokal dan lebih mengutamakan solusi yang sudah ada.

• Algoritma yang selalu memilih solusi dengan biaya paling rendah pada setiap langkah.

Tujuan utama dari algoritma greedy …

• Mengoptimalkan penggunaan memori dalam komputer.

• Menyelesaikan masalah dengan langkah-langkah yang optimal pada setiap tahap.

• Mengurangi jumlah langkah yang diperlukan untuk menyelesaikan masalah.

• Memecahkan masalah dengan memilih solusi terbaik secara global.

• Mencari solusi yang selalu memberikan hasil terbaik secara keseluruhan.

Dengan algoritma greedy, kita diberikan masalah untuk sejumlah koin dengan denominasi yang berbeda dan suatu jumlah uang yang ingin dicapai. Bagaimana algoritma greedy akan memilih koin untuk mencapai jumlah tersebut …

• Pilih koin dengan nilai terkecil terlebih dahulu.

• Pilih koin dengan nilai terbesar terlebih dahulu.

• Pilih koin yang paling sering digunakan oleh orang lain.

• Pilih koin secara acak.

• Pilih koin berdasarkan urutan waktu kedatangan.

Greedy secara harfiah berarti …

• Cerdas atau pintar

• Serakah atau rakus

• Cepat atau tangkas

• Bijaksana atau hati-hati

• Sederhana atau efisien

Dalam masalah pembagian pekerjaan ke mesin dengan kapasitas terbatas, Anda memiliki lima pekerjaan dengan durasi waktu sebagai berikut:

-

Jika kapasitas tiap mesin adalah 5 jam, mana urutan pekerjaan yang pertama kali dipilih untuk dimasukkan ke mesin yang masih di bawah kapasitas mesin 5 jam …

• Pekerjaan 1, Pekerjaan 2

• Pekerjaan 3, Pekerjaan 5

• Pekerjaan 1, Pekerjaan 3

• Pekerjaan 4, Pekerjaan 1

• Pekerjaan 2, Pekerjaan 5

Tugas Anda adalah mengalokasikan pekerjaan ke mesin, dengan kapasitas mesin 6 jam. Berikut adalah daftar pekerjaan dengan waktu pengerjaannya:

• -

• Menggunakan algoritma greedy, tentukan pekerjaan mana yang akan dimasukkan dalam mesin pertama …

• Pekerjaan 1, Pekerjaan 5

• Pekerjaan 1, Pekerjaan 2

• Pekerjaan 2, Pekerjaan 5

• Pekerjaan 3, Pekerjaan 1

• Pekerjaan 4, Pekerjaan 5

Budi ingin membawa beberapa ekor ikan yang sudah tersimpan dalam kantong-kantong plastik untuk diangkut di dalam mobilnya. Terdapat 8 buah kantong dengan yang berisi masing-masing 3, 5, 2, 8, 4, 6, 6, dan 3 ekor ikan. Namun sayangnya, mobilnya hanya mampu membawah 4 buah kantong. Kantong-kantong manakah yang harus dibawa oleh Budi agar jumlah ikan yang dibawanya sebanyak mungkin …

• 8 + 6 + 6 + 5

• 6 + 5 + 4 + 3

• 8 + 6 + 5 + 4

• 6 + 6 + 5 + 4

• 8 + 6 + 5 + 3

Terdapat 8 buah kantong dengan yang berisi masing-masing 3, 5, 2, 8, 4, 6, 6, dan 3 ekor ikan. Budi harus membawa sedikitnya 15 ekor ikan. Tentukan jumlah kantong terkecil yang harus dibawa oleh Budi, agar terdapat minimal 15 ekor ikan yang terbawa …

• 5 kantong

• 4 kantong

• 3 kantong

• 2 kantong

• 1 kantong

Dalam suatu proyek, ada beberapa pekerjaan yang harus diselesaikan dengan durasi yang berbeda-beda, namun hanya ada satu mesin yang bisa digunakan untuk menyelesaikan pekerjaan tersebut. Untuk mengoptimalkan penggunaan mesin, algoritma greedy memilih pekerjaan berdasarkan durasi yang paling singkat terlebih dahulu. Setelah beberapa pekerjaan diselesaikan, terdapat beberapa pekerjaan yang tersisa dengan durasi yang lebih panjang. Jika kita mengganti strategi dan memilih pekerjaan dengan durasi lebih panjang terlebih dahulu, apa yang kemungkinan akan terjadi terhadap total waktu yang diperlukan untuk menyelesaikan semua pekerjaan …

• Waktu total yang diperlukan akan lebih singkat karena pekerjaan yang lebih lama diselesaikan lebih dulu.

• Waktu total yang diperlukan akan lebih lama karena pekerjaan yang lebih lama diselesaikan lebih dulu, tetapi dapat mengurangi waktu tunda untuk pekerjaan lainnya.

• Waktu total yang diperlukan tidak akan berubah, karena algoritma greedy tetap efisien dalam memilih pekerjaan.

• Waktu total yang diperlukan akan lebih lama karena pekerjaan yang lebih panjang mengurangi waktu kosong untuk pekerjaan berikutnya.

• Waktu total yang diperlukan akan tetap sama, namun pekerjaan yang lebih lama lebih mudah diselesaikan setelah pekerjaan pendek selesai.

Anda diberikan sejumlah barang dengan nilai dan bobot yang berbeda serta kapasitas tas yang terbatas. Anda menggunakan algoritma greedy dengan memilih barang berdasarkan rasio nilai terhadap bobot terbesar terlebih dahulu. Namun, setelah Anda menyelesaikan pemilihan barang pertama, Anda menemukan bahwa kapasitas tas yang tersisa tidak cukup untuk barang berikutnya yang memiliki rasio nilai terhadap bobot yang lebih kecil. Apa yang mungkin menyebabkan algoritma greedy gagal dalam memberikan solusi optimal untuk masalah ini …

• Algoritma greedy memilih barang dengan rasio nilai terhadap bobot terbesar, yang tidak selalu mencerminkan kombinasi optimal

• Algoritma greedy tidak mempertimbangkan total nilai dari semua barang yang dipilih, hanya berdasarkan barang yang memiliki rasio terbaik.

• Rasio nilai terhadap bobot barang pertama tidak mencerminkan nilai total tas yang akan diisi.

• Algoritma greedy mengabaikan barang dengan bobot ringan karena lebih memilih barang dengan bobot besar.

• Kapasitas tas yang terbatas menyebabkan algoritma greedy gagal memilih barang dengan cara yang optimal, meskipun menggunakan rasio terbaik.