Problema del cambio delle monete
Lezione 8 di 15 del corso Programmazione dinamica 101 di Coddy.
Il problema del resto è un classico problema di programmazione dinamica. Data una serie di monete con tagli diversi e una somma totale di denaro, il compito consiste nel trovare il numero minimo di monete necessario per comporre la somma indicata.
Ad esempio, supponiamo di avere monete con i tagli [1, 5, 10] e di voler comporre la somma 15. Il numero minimo di monete necessario sarebbe 2 (una moneta da 10 e una moneta da 5).
Per risolvere questo problema usando la programmazione dinamica, possiamo creare una tabella con righe che rappresentano i tagli delle monete e colonne che rappresentano gli importi da 0 alla somma totale indicata. Poi compiliamo la tabella procedendo dal basso verso l’alto, calcolando il numero minimo di monete necessario per comporre ciascun importo usando le monete di ogni taglio.
Sfida
MedioScrivi un programma che accetta due input: un elenco di tagli di monete e un importo obiettivo, e restituisce il numero minimo di monete necessario per comporre l'importo obiettivo.
Ad esempio, per i tagli [1, 5, 10] e l'importo obiettivo 15, l'output dovrebbe essere 2.
Provalo tu
def min_coins(coins, target):
# Scrivi il codice quiTutte le lezioni di Programmazione dinamica 101
1Introduzione alla DP
Che cos’è la programmazione dinamica?Perché è importante?Applicazioni in vari campi3Algoritmi di programmazione dinamica
Sottosequenza comune più lungaProblema dello zainoProblema del cambio delle moneteDistanza di modificaEsercitati da solo: Compilatore Python online