Masalah penukaran koin
Pelajaran 8 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Masalah penukaran koin adalah masalah klasik dalam pemrograman dinamis. Dengan sekumpulan koin yang memiliki pecahan berbeda dan jumlah uang total, tugasnya adalah mencari jumlah minimum koin yang diperlukan untuk mencapai jumlah tersebut.
Contohnya, misalkan kita memiliki koin dengan pecahan [1, 5, 10] dan ingin mencapai jumlah 15. Jumlah minimum koin yang diperlukan adalah 2 (satu koin 10 dan satu koin 5).
Untuk menyelesaikan masalah ini menggunakan pemrograman dinamis, kita dapat membuat tabel dengan baris yang mewakili pecahan koin dan kolom yang mewakili jumlah dari 0 hingga jumlah total tersebut. Kemudian, kita mengisi tabel dari bawah ke atas dengan menghitung jumlah minimum koin yang diperlukan untuk mencapai setiap jumlah menggunakan koin dari setiap pecahan.
Tantangan
SedangTulis program yang menerima dua input: list pecahan koin dan jumlah target, lalu mengembalikan jumlah minimum koin yang diperlukan untuk mencapai jumlah target.
Misalnya, untuk pecahan koin [1, 5, 10] dan jumlah target 15, output-nya harus 2.
Coba sendiri
def min_coins(coins, target):
# Tulis kodemu di siniSemua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online