Menurut kalian, apakah permasalahan penukaran uang pada aktivitas SAP-K11-06-U: Menukarkan Uang

Menurut kalian, apakah permasalahan penukaran uang pada aktivitas SAP-K11 06-U: Menukarkan Uang untuk topik greedy sebelumnya (yaitu pecahan yang tersedia hanya 1000, 7000 dan 10000, dan kita ingin menukarkan nilai 15.000)  dapat diselesaikan dengan teknik pemrograman dinamis? Bagaimana caranya?

Jawaban:

Ya, permasalahan penukaran uang pada aktivitas SAP-K11-06-U: Menukarkan Uang dengan pecahan yang tersedia (1000, 7000, dan 10000) untuk nilai 15000 dapat diselesaikan menggunakan teknik pemrograman dinamis.

Berikut adalah langkah-langkahnya:

1. Tentukan nilai-nilai pecahan yang tersedia dan jumlah pecahan yang dibutuhkan untuk setiap nilai tersebut. Dalam kasus ini, pecahan yang tersedia adalah 1000, 7000, dan 10000.

2. Buat sebuah tabel dengan jumlah baris sebanyak nilai yang ingin ditukarkan (dalam kasus ini, 15000) dan jumlah kolom sebanyak jumlah pecahan yang tersedia (dalam kasus ini, 3).

3. Setiap sel pada tabel akan menyimpan jumlah minimum pecahan yang dibutuhkan untuk mencapai nilai tertentu. Awalnya, seluruh sel pada tabel diisi dengan nilai tak terhingga, kecuali sel pada baris pertama dan kolom pertama yang diisi dengan 0.

4. Mulai dari baris kedua, lakukan iterasi untuk setiap nilai dari 1 hingga nilai yang ingin ditukarkan (dalam kasus ini, 15000). Untuk setiap nilai, lakukan iterasi untuk setiap pecahan yang tersedia.

5. Pada setiap langkah iterasi, periksa apakah nilai pecahan saat ini lebih kecil atau sama dengan nilai yang ingin ditukarkan. Jika iya, cari nilai minimum antara jumlah pecahan yang dibutuhkan untuk mencapai nilai sebelumnya (nilai - pecahan saat ini) dan jumlah pecahan yang dibutuhkan pada baris sebelumnya untuk pecahan yang sama.

6. Isi sel pada baris dan kolom saat ini dengan nilai minimum yang ditemukan pada langkah sebelumnya.

7. Setelah selesai iterasi, nilai pada sel terakhir di baris terakhir akan memberikan jumlah pecahan minimum yang dibutuhkan untuk mencapai nilai yang ingin ditukarkan (dalam kasus ini, 15000).