Kunci Jawaban Informatika Kelas 11 Halaman 34 35 Kurikulum Merdeka, Ayo Berlatih: Menukarkan Uang

Jelas bahwa jumlah total lembaran yang dibutuhkan tergantung dari pemilihan pecahan uang yang kita gunakan. 

Nah, permasalahan yang mungkin kita tanyakan adalah:

Bagaimana caranya memilih pecahan-pecahan uang yang akan digunakan sedemikian rupa, sehingga total lembaran yang diperlukan untuk menghasilkan suatu nilai uang tertentu
menjadi sekecil mungkin?

Pada contoh di atas, dapat diperiksa bahwa untuk menghasilkan nilai uang sebesar tiga puluh delapan ribu rupiah dari pecahan-pecahan seribuan, dua ribuan, lima ribuan, sepuluh ribuan dan dua puluh ribuan, maka diperlukan minimal 5 buah lembar, yaitu sesuai dengan cara terakhir
di atas. 

Dapatkah Anda mencari strategi yang umum untuk menyelesaikan permasalahan serupa, jika jumlah nilai uang yang dihasilkan berbeda (namun dengan pecahan-pecahan uang yang sama)? 

Kita bisa menganggap bahwa jumlah nilai yang diinginkan selalu merupakan kelipatan ribuan rupiah
(sehingga selalu bisa didapatkan dengan menggabungkan pecahan-pecahan di atas).

Kunci Jawaban:

Untuk menyelesaikan permasalahan ini, kita dapat menerapkan algoritma greedy sebagai berikut: kita lakukan beberapa langkah untuk memilih pecahan yang diambil, sampai didapatkan jumlah yang diperlukan:

Berikut adalah contoh penerapan strategi ini untuk mencari jumlah lembaran uang yang diperlukan untuk mendapatkan nilai 38 ribu rupiah menggunakan pecahan-pecahan yang sama:

1. Urutan pecahan: 20 ribu, 10 ribu, 5 ribu, 2 ribu, 1 ribu.
2.  Inisialisasi jumlah lembaran uang: 0.

Mulai dengan pecahan uang 20 ribu:

Bagi 38 ribu dengan 20 ribu = 1 (tanpa sisa).
Tambahkan 1 ke jumlah lembaran uang: 0 + 1 = 1.
Perbarui jumlah yang diinginkan dengan sisa: 38 ribu – (1 × 20 ribu) = 18 ribu.

Lanjutkan dengan pecahan uang 10 ribu:

Bagi 18 ribu dengan 10 ribu = 1 (tanpa sisa).
Tambahkan 1 ke jumlah lembaran uang: 1 + 1 = 2.
Perbarui jumlah yang diinginkan dengan sisa: 18 ribu – (1 × 10 ribu) = 8 ribu.

Lanjutkan dengan pecahan uang 5 ribu: