Latihan Soal Algoritma Greedy Informatika Fase F Kelas XI Semester 1

Soal 1:

Jelaskan prinsip dasar dari algoritma greedy. Berikan contoh kasus di mana algoritma greedy dapat digunakan untuk menyelesaikan masalah, dan jelaskan langkah-langkah penyelesaiannya.

Soal 2:
Diberikan sejumlah koin dengan denominasi {1, 5, 10, 25}. Bagaimana algoritma greedy dapat digunakan untuk membuat jumlah uang minimal dengan koin-koin ini jika Anda harus membentuk jumlah 63? Jelaskan langkah-langkah algoritma dan berapa jumlah koin yang dibutuhkan.

Soal 3:
Anda memiliki sebuah ransel yang memiliki kapasitas maksimal 50 kg. Diberikan barang-barang dengan berat dan nilai sebagai berikut:

• Barang A: Berat 10 kg, Nilai 60
• Barang B: Berat 20 kg, Nilai 100
• Barang C: Berat 30 kg, Nilai 120

Bagaimana algoritma greedy dapat digunakan untuk memaksimalkan nilai total yang dapat dimasukkan ke dalam ransel? Jelaskan proses pemilihan barang dan hasil akhirnya.

Soal 4:
Anda harus mengatur serangkaian tugas dengan waktu mulai dan selesai sebagai berikut:

• Tugas 1: mulai 1, selesai 3
• Tugas 2: mulai 2, selesai 5
• Tugas 3: mulai 4, selesai 6
• Tugas 4: mulai 6, selesai 8
• Tugas 5: mulai 5, selesai 7

Bagaimana algoritma greedy dapat digunakan untuk memilih jumlah tugas maksimal yang tidak saling tumpang tindih? Tunjukkan langkah-langkah dalam memilih tugas.

Soal 5:
Dalam sebuah graf berbobot dengan 5 node, Anda diminta menemukan Minimum Spanning Tree (MST) menggunakan algoritma greedy (misalnya, Algoritma Kruskal atau Prim). Graf terseut memiliki bobot tepi sebagai berikut:

• (A-B: 2), (A-C: 3), (B-C: 1), (B-D: 4), (C-D: 5), (C-E: 6), (D-E: 7)

Tunjukkan langkah-langkah algoritma greedy untuk menemukan MST, dan berikan total bobot dari MST tersebut.