Errori tipici · In sintesi¶

28.4 Errori tipici¶

Attenzione

Contare i vettori invece degli schemi di taglio. I \(2^{n-1}\) schemi di taglio di un'asta di lunghezza \(n\) sono più dei vettori soluzione quando \(n\ge 3\), perché schemi diversi possono dare lo stesso vettore.
Dimenticare il caso base. \(v(0)=0\) si usa quando il primo pezzo ha la lunghezza dell'intera asta: \(v(\ell)\) contiene il termine \(p_\ell+v(0)\).
Usare la riga \(j-1\) nella seconda ricorrenza. Il termine \(p_j+v(j,\ell-j)\) resta nella riga \(j\): altrimenti ogni lunghezza dei pezzi si potrebbe tagliare una sola volta.
Fermare la ricostruzione troppo presto. La regola \(x_{{s}[\ell]}\leftarrow x_{{s}[\ell]}+1\), \(\ell\leftarrow\ell-{s}[\ell]\) si ripete finché \(\ell=0\); l'ultimo pezzo completa l'asta.

In sintesi

L'RCP chiede come tagliare un'asta di lunghezza \(n\) in pezzi, con ogni lunghezza disponibile un numero qualsiasi di volte, per massimizzare il profitto totale.
La ricorrenza \(v(\ell)=\max_{j\le\ell}\{p_j+v(\ell-j)\}\) ha sottostruttura ottima e sottoproblemi sovrapposti, e \(v(0)=0\).
Il vettore \(v\) si riempie bottom-up in \(\Theta(n^2)\) passi, un numero polinomiale perché l'input contiene \(n\) profitti.
Il vettore \({s}\) dei primi pezzi dà una soluzione ottima per ogni lunghezza dell'asta senza costi aggiuntivi.

Quadro riassuntivo dell'esempio dell'RCP. Esempio 28.1 (asta di lunghezza \(4\)):

Metodo	Lower bound	Upper bound	Origine
Algoritmo di PD	\(10\)	\(10\)	valore ottimo, due pezzi di lunghezza \(2\)

Esercizi su questo capitolo: Taglio delle aste (RCP)