Baca tanpa iklan
Dapat dipahami bahwa pada setiap langkah, kita menerapkan algoritma greedy dengan mencari pecahan terbesar yang masih bisa diambil tanpa melewati besaran nilai yang diinginkan. Dengan memilih pecahan terbesar pada setiap langkah, kita dijamin akan meminimalkan banyaknya pecahan yang diperlukan.
Namun, perlu ditekankan dan dipahami bahwa pendekatan greedy tidak selalu dijamin berhasil, apabila nominal pecahan-pecahan uangnya diubah. Misalnya, andaikan bahwa pecahan yang tersedia bernilai seribuan, 13 ribuan dan dua puluh ribuan. Maka, jika kita ingin mencapai nilai 27 ribu rupiah, pendekatan secara greedy akan menghasilkan solusi = 1 lembar dua puluh ribuan dan 7 lembar seribuan, dengan total 8 lembar pecahan. Padahal, kita dapat menggunakan dua lembar 13 ribuan ditambah 1 lembar seribuan, dengan total 3 lembar pecahan. Jadi, untuk permasalahan seperti ini, perlu dipastikan bahwa memang pendekatan greedy menghasilkan solusi yang benar-benar optimal. Apabila tidak, maka solusi dengan pendekatan lain, misalnya dengan menggunakan pemrograman dinamis (dynamic programming), mungkin lebih cocok untuk diterapkan pada permasalahan tersebut.
Disclaimer:
- Kunci jawaban Informatika di atas hanya digunakan oleh orang tua atau wali untuk memandu proses belajar anak.
- Sebelum melihat kunci jawaban, pastikan anak mengerjakan sendiri terlebih dahulu.
(Tribunnews.com/Rinanda)