Errori tipici · In sintesi¶

17.4 Errori tipici¶

Attenzione

Aggiornare il vettore unico in ordine crescente di capacità. La cella \({v}[k-w_j]\) conterrebbe già la riga \(j\) e l'oggetto \(j\) potrebbe essere selezionato più di una volta; le capacità si scorrono a partire da \(c\) verso il basso.
Dimenticare i casi base. Senza oggetti disponibili il valore ottimo è \(0\) per ogni capacità: \(v(0,k)=0\) per ogni \(k \in \{0,1,\dots,c\}\), non solo per \(k=0\).
Ricostruire con l'indice sbagliato. A ogni passo l'indice dell'oggetto diminuisce di uno, mentre la capacità diminuisce di \(w_j\) solo se l'oggetto \(j\) è selezionato.
Chiamare polinomiale \(\Theta(nc)\). La capacità \(c\) si scrive con \(\log c\) cifre, quindi il tempo di esecuzione è esponenziale nella dimensione dell'input.
Leggere \(u(n,q)\) come il valore ottimo. Nel secondo algoritmo di PD \(u(n,q)\) è un peso minimo; il valore ottimo è il più grande \(q\) con \(u(n,q)\le c\).

In sintesi

La ricorrenza \(v(j,k)\) sceglie fra lasciare fuori l'oggetto \(j\) e prenderlo; ha la sottostruttura ottima e i sottoproblemi sovrapposti.
La matrice si riempie bottom-up in \(\Theta(nc)\) passi; un solo vettore scorso verso il basso dà il valore ottimo con sole \(c+1\) celle.
Una soluzione ottima si ricava dalla matrice \({s}\) delle decisioni, letta all'indietro a partire da \((n,c)\).
Il tempo di esecuzione \(\Theta(nc)\) è pseudopolinomiale; le liste di stati non dominati memorizzano solo gli stati raggiungibili.
Scambiando profitti e pesi si ottengono \(\Theta(nP)\) passi, il che è meglio quando il profitto totale \(P\) è piccolo.

Cruscotto dell'esempio del KP. L'Esempio 17.1 (\(c=5\), tre oggetti) con i bound trovati finora:

Metodo	Lower bound	Upper bound	Origine
Algoritmo di PD	\(14\)	\(14\)	valore ottimo, \(\Theta(nc)\) passi

Esercizi su questo capitolo: Zaino 0/1 (KP)