Problema del taglio delle aste (RCP)

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

Definizione 1: Problema del taglio delle aste

Dati:

1. un'asta di lunghezza \(n \in \Z_{\ge 1}\),

2. un insieme \(\{1,2,\dots,n\}\) di \(n\) possibili lunghezze dei pezzi,

3. per ogni lunghezza \(\ell \in \{1,2,\dots,n\}\), un profitto \(p_\ell \in \Z_{\ge 1}\),

il problema del taglio delle aste (RCP) chiede di decidere quanti pezzi di ogni lunghezza tagliare, in modo che la lunghezza totale dei pezzi ottenuti sia uguale alla lunghezza dell'asta, e il profitto totale dei pezzi ottenuti sia massimo.

Che cosa fa il corso su questo problema

Tecnica	Dove
Definizione	Questa pagina
Programmazione dinamica	Cap. 16 «Principi della programmazione dinamica»; Cap. 28 «PD per il problema del taglio delle aste»
Esercizi	Cap. 28 (5 esercizi)