Errori tipici · In sintesi¶

18.4 Errori tipici¶

Attenzione

Usare la riga \(j-1\) nella seconda ricorrenza. Il termine \(p_j+v(j,k-w_j)\) si riferisce alla stessa riga \(j\): è questo che consente più copie del tipo di oggetto \(j\).
Supporre che la capacità sia riempita. Una parte della capacità può restare inutilizzata: quando nessun tipo di oggetto entra, \(v(k)=0\), non \(-\infty\); nell'Esempio 18.1, \(v(1)=0\).
Ricostruire oltre la fine. La ricostruzione si ferma quando la capacità residua è \(0\), oppure quando \(s[k]=0\) nel primo algoritmo di PD e \(j=0\) nel secondo; altrimenti si legge fuori dai vettori.
Dimenticare il caso base. \(v(0)=0\), e \(v[0..c]\) ha \(c+1\) celle, non \(c\).

In sintesi

Nell'UKP un tipo di oggetto si può usare un numero qualsiasi di volte, quindi il valore ottimo dipende solo dalla capacità residua: \(v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}\).
Il primo algoritmo di PD riempie un vettore di \(c+1\) celle in \(\Theta(nc)\) passi; il secondo riempie la matrice \(v(j,k)\) e riusa la stessa riga per le copie successive.
Una soluzione ottima si legge all'indietro dalle informazioni memorizzate, fermandosi quando la capacità residua è nulla o inutilizzata.
Il tempo di esecuzione è pseudopolinomiale, come per il KP.

Cruscotto dell'esempio dell'UKP. L'Esempio 18.1 (\(c=7\), quattro tipi di oggetto):

Metodo	Lower bound	Upper bound	Origine
Algoritmo di PD	\(14\)	\(14\)	valore ottimo, soluzione \((1,0,1,0)\)

Esercizi su questo capitolo: Zaino illimitato (UKP)