Problemi misti

Catalogo dei problemi di ottimizzazione combinatoria · Catalogo (PDF)

• Nel problema del taglio delle aste un'asta di lunghezza \(n\) è tagliata in pezzi di lunghezza intera \(\ell\) con profitti \(p_\ell\); la lunghezza totale dei pezzi è uguale a \(n\) e il loro profitto totale è massimo.

• Nel problema del cambio monete si restituisce un resto \(c\) con monete dei tagli \(w_1,\dots,w_n\), ciascuno disponibile in quantità illimitata; il valore totale è uguale a \(c\) e il numero di monete è minimo.

Problema	Sigla	Differenza
Problema del taglio delle aste	RCP	Uno zaino illimitato con un tipo di oggetto per ogni lunghezza \(\ell\) dei pezzi, peso \(\ell\), profitto \(p_\ell\) e capacità \(n\), in cui la lunghezza totale deve essere esattamente \(n\).
Problema del cambio monete	CCP	Come l'UKP ha copie illimitate di ogni tipo di oggetto, ma chiede esattamente \(c\) e minimizza il numero di monete, mentre l'UKP chiede al più \(c\) e massimizza il profitto.