PD per il problema dello zaino 0/1

Parte 3 · Programmazione dinamica · Capitolo 17 · Dispensa, volume 3 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Zaino 0/1 (KP) · App: Tabelle della PD per i problemi di zaino

Prerequisiti

• Da questo modulo, il capitolo «Principi della programmazione dinamica»: sottostruttura ottima, sottoproblemi sovrapposti, relazioni di ricorrenza, casi base e approcci top-down e bottom-up.

• Da questo modulo, il capitolo «Problemi di zaino»: il problema dello zaino 0/1 (KP), la codifica binaria di una soluzione e i \(2^n\) sottoinsiemi di oggetti.

• Dal modulo Algoritmi: come si legge lo pseudocodice (Capitolo 2) e la dimensione dell'input di un algoritmo (Capitolo 11) (serve a spiegare perché \(\Theta(nc)\) è pseudopolinomiale).

Dove eravamo

• Come problema: il KP, le sue istanze e i \(2^n\) sottoinsiemi (capitolo «Problemi di zaino»).

• Come modello: il modello PLI, il suo rilassamento lineare e i bound duali (capitolo «Formulazioni dei problemi di zaino»).

• Ora, come tabella: l'algoritmo di PD calcola esattamente il valore ottimo, senza modello e senza solver.

Obiettivi

Al termine di questo capitolo saremo in grado di:

• scrivere la ricorrenza \(v(j,k)\) del KP, spiegare perché è corretta e calcolare a mano la tabella con l'approccio top-down, con l'approccio bottom-up e con un solo vettore;

• ricostruire una soluzione ottima dalla matrice \({s}\) delle decisioni;

• contare i passi dell'algoritmo di PD e spiegare perché \(\Theta(nc)\) è pseudopolinomiale e non polinomiale;

• descrivere gli stati \((w,p)\), scartare quelli dominati ed eseguire l'algoritmo di PD su liste di stati;

• scambiare i ruoli di profitti e pesi e calcolare il valore ottimo dalla tabella \(u(j,q)\).

Il problema di questo capitolo è il problema dello zaino 0/1 (KP): la sua definizione e le sue ipotesi sono nella sua pagina.

17.1 Istanze e soluzioni ammissibili

Esempio 17.1: Istanza del KP

Consideriamo uno zaino di capacità \(c = 5\) e un insieme \(\{1,2,3\}\) di \(3\) oggetti (\(n = 3\)), con i seguenti profitti e pesi:

\[ \begin{array}{l|rrr} \hline & {j = 1} & {j = 2} & {j = 3} \\ \hline {p_j} & {6} & {7} & {8} \\ {w_j} & {2} & {3} & {3} \\ \hline \end{array} \]

Chiamiamo questa istanza del KP Esempio 17.1.

Il numero di possibili sottoinsiemi di oggetti è \(2^n\) poiché, per ogni oggetto, possiamo scegliere in modo indipendente se inserirlo o no nello zaino. Alcuni sottoinsiemi possono non rispettare la capacità dello zaino. Di conseguenza, il numero di soluzioni ammissibili è al più \(2^n\).

• Il numero di possibili soluzioni del KP cresce esponenzialmente con il numero \(n\) di oggetti. Pertanto, l'enumerazione di tutte le possibili soluzioni diventa presto impraticabile al crescere di \(n\).

17.1.1 Codifica delle soluzioni ammissibili

Una soluzione ammissibile del KP è un sottoinsieme di oggetti il cui peso totale non supera la capacità dello zaino.

• Una soluzione ammissibile del KP si può descrivere con il vettore binario

  \[ (x_1,x_2,\dots,x_n) \]

  dove ogni componente ha il seguente significato:

  \[ x_j = \left\{ \begin{array}{ll} 1 & \textrm{se l'oggetto } j \textrm{ è selezionato,}\\[1ex] 0 & \textrm{altrimenti,} \end{array} \right. \qquad \forall j \in \{1,2,\dots,n\}. \]

  Poiché la soluzione è ammissibile, il peso totale degli oggetti selezionati non deve superare la capacità dello zaino:

  \[ \sum_{j=1}^{n} w_j x_j \le c. \]

  Il profitto totale di una soluzione ammissibile è

  \[ \sum_{j=1}^{n} p_j x_j. \]

Esempio 17.2: Enumerazione di tutte le possibili soluzioni del KP

Consideriamo l'istanza del KP dell'Esempio 17.1, con uno zaino di capacità \(c=5\) e i seguenti profitti e pesi:

\[ \begin{array}{l|rrr} \hline & {j = 1} & {j = 2} & {j = 3} \\ \hline {p_j} & {6} & {7} & {8} \\ {w_j} & {2} & {3} & {3} \\ \hline \end{array} \]

Ci sono \(2^3 = 8\) possibili sottoinsiemi di oggetti, corrispondenti ai diversi modi di selezionare o non selezionare gli oggetti.

Nel seguente albero binario ogni livello corrisponde a un oggetto: un arco con etichetta \(1\) indica che l'oggetto è selezionato, mentre un arco con etichetta \(0\) indica che non è selezionato. Ogni foglia rappresenta un sottoinsieme completo di oggetti e riporta il vettore corrispondente.

La figura seguente mostra i sottoinsiemi associati alle foglie dell'albero, tramite le etichette \((1),(2),\ldots,(8)\). Per ogni oggetto selezionato, il numero scritto dentro il parallelepipedo è il suo peso, mentre il numero sopra è il suo profitto. La larghezza di ogni parallelepipedo è proporzionale al peso dell'oggetto. I sottoinsiemi il cui peso totale supera la capacità dello zaino sono indicati come non ammissibili.

Etichetta	Vettore soluzione	Peso totale	Profitto totale	Ammissibile?
\((1)\)	\((0,0,0)\)	\(0\)	\(0\)	sì
\((2)\)	\((1,0,0)\)	\(2\)	\(6\)	sì
\((3)\)	\((0,1,0)\)	\(3\)	\(7\)	sì
\((4)\)	\((0,0,1)\)	\(3\)	\(8\)	sì
\((5)\)	\((1,1,0)\)	\(2+3=5\)	\(6+7=13\)	sì
\((6)\)	\((1,0,1)\)	\(2+3=5\)	\(6+8=14\)	sì
\((7)\)	\((0,1,1)\)	\(3+3=6\)	\(7+8=15\)	no
\((8)\)	\((1,1,1)\)	\(2+3+3=8\)	\(6+7+8=21\)	no

• Panoramica

  Istanze e soluzioni ammissibili · Codifica delle soluzioni ammissibili

  Apri

• 17.2 Un primo algoritmo di PD

  Apri

• 17.2.2 Un primo algoritmo di PD: Un'implementazione con liste

  Apri

• 17.3 Un secondo algoritmo di PD

  Apri

• 17.3.2 Un secondo algoritmo di PD: Un'implementazione con liste

  Apri

• Errori tipici · In sintesi

  In sintesi

  Apri

---

Avanti: 17.2 Un primo algoritmo di PD

---

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

Nel laboratorio interattivo: Tabelle della PD per i problemi di zaino.