Problema del cambio monete (CCP)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi misti · Catalogo (PDF)

Definizione 1: Problema del cambio monete

Dati:

1. un vettore \(w \in \Z_{\ge 1}^n\) di \(n\) tagli, ciascuno disponibile in quantità illimitata,

2. un resto intero \(c \in \Z_{\ge 0}\) da restituire,

il problema del cambio monete (CCP) chiede di decidere quante monete di ogni taglio usare in modo che il loro valore totale sia esattamente uguale a \(c\), e il numero totale di monete usate sia minimo. Se nessuna combinazione di monete restituisce esattamente \(c\), l'istanza è non ammissibile.

Che cosa fa il corso su questo problema

Tecnica	Dove
Definizione	Questa pagina
Programmazione dinamica	Cap. 16 «Principi della programmazione dinamica»; Cap. 27 «PD per il problema del cambio monete»
Esercizi	Cap. 27 (5 esercizi)