PD per il problema dello zaino a scelta multipla

Parte 3 · Programmazione dinamica · Capitolo 21 · Dispensa, volume 3 (PDF) · Slide · Esercizi: Zaino a scelta multipla (MCKP)

Prerequisiti

• Da questo modulo, il capitolo «PD per il problema dello zaino 0/1»: la ricorrenza \(v(j,k)\) del problema dello zaino 0/1 (KP) su oggetti e capacità, la matrice \(s\) delle decisioni e la ricostruzione di una soluzione.

• Da questo modulo, il capitolo «Problemi di zaino»: il problema dello zaino a scelta multipla, le sue classi \(\mathscr{J}_h\) e la sua condizione di ammissibilità.

• Dal modulo Algoritmi: le convenzioni dello pseudocodice (Capitolo 2) e la dimensione dell'input (Capitolo 11).

Obiettivi

Al termine di questo capitolo saremo in grado di:

• scrivere la ricorrenza \(v(h,k)\) su classi e capacità, con il valore \(-\infty\) per le sottoistanze senza soluzione ammissibile;

• eseguire a mano l'algoritmo di PD, provando ogni oggetto della classe \(h\) che entra nello zaino;

• riempire la matrice \(s\) degli oggetti scelti e ricostruire una soluzione ottima, un oggetto per classe;

• contare i \(\Theta(nc)\) passi dell'algoritmo di PD.

Il problema di questo capitolo è il problema dello zaino a scelta multipla (MCKP): la sua definizione e le sue ipotesi sono nella sua pagina.

21.1 Un algoritmo di PD

Esempio 21.1: Istanza dell'MCKP

Consideriamo uno zaino di capacità \(c=10\) e un insieme \(\mathscr{I}=\{1,2,\dots,7\}\) di \(7\) oggetti (\(n=7\)), partizionato in \(q=3\) classi: \(\mathscr{J}_1=\{1,2\}\), \(\mathscr{J}_2=\{3,4,5\}\) e \(\mathscr{J}_3=\{6,7\}\). I profitti e i pesi sono:

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

Chiamiamo questa istanza dell'MCKP Esempio 21.1.

• Una soluzione ammissibile sceglie esattamente un oggetto in ogni classe, quindi si descrive con il sottoinsieme selezionato \(S\subseteq\mathscr{I}\), con \(|S\cap\mathscr{J}_h|=1\) per ogni classe \(h\), oppure con il vettore binario \((x_1,x_2,\dots,x_n)\) di \(S\).

• Le classi sono gli stadi dell'algoritmo di PD: la classe \(h\) si decide dopo le classi \(1,2,\dots,h-1\), e la sua decisione è l'oggetto scelto in essa.

• Passo 1: calcolo del valore ottimo

  Per ogni \(h \in \{0,1,\dots,q\}\) e \(k \in \{0,1,\dots,c\}\), sia \(v(h,k)\) il valore ottimo della sottoistanza dell'MCKP data da:

  1. uno zaino di capacità \(k\),

  2. le classi \(\mathscr{J}_1,\mathscr{J}_2,\dots,\mathscr{J}_h\),

  3. per ogni oggetto \(j \in \mathscr{J}_1\cup\mathscr{J}_2\cup\dots\cup\mathscr{J}_h\), un profitto \(p_j\) e un peso \(w_j\),

  con \(v(h,k)=-\infty\) se questa sottoistanza non ha soluzioni ammissibili.

  La formula ricorsiva per calcolare \(v(h,k)\) è la seguente:

  \[\begin{equation*} \label{eq:mckp} v(h,k)= \left\{ \begin{array}{ll} 0 & \textrm{se $h=0$,}\\[2ex] -\infty & \begin{array}[t]{@{}l@{}}\textrm{se $h\ge 1$ e}\\ \textrm{$\forall j\in\mathscr{J}_h$: $w_j>k$,}\end{array}\\[4ex] \displaystyle \max_{j \in \mathscr{J}_h:\, w_j \le k} \big\{ p_j + v(h-1,k-w_j) \big\} & \begin{array}[t]{@{}l@{}}\textrm{se $h\ge 1$ e}\\ \textrm{$\exists j\in\mathscr{J}_h$: $w_j\le k$.}\end{array} \end{array} \right. \tag{21.1} \end{equation*}\]

  • Il valore \(-\infty\) segue le regole \(p_j+(-\infty)=-\infty\) e \(\max\{-\infty,a\}=a\): una sottoistanza senza soluzioni ammissibili non dà mai un valore migliore.

  • I casi base sono \(v(0,k)=0\) per ogni \(k\): senza classi, il sottoinsieme vuoto è ammissibile e ha profitto \(0\), qualunque sia la capacità.

  • La formula \(\eqref{eq:mckp}\) genera al più \(|\mathscr{J}_h|\) sottoproblemi indipendenti, uno per ogni oggetto \(j\) della classe \(h\) che entra nella capacità \(k\): il sottoproblema residuo ha le classi \(1,2,\dots,h-1\) e la capacità \(k-w_j\).

  • Quindi una soluzione ottima per \((h,k)\) si costruisce combinando il miglior oggetto \(j\) della classe \(h\) con una soluzione ottima del suo sottoproblema residuo.

    \(\rightsquigarrow\) Sottostruttura ottima verificata!

  • Scelte diverse nelle classi \(h+1,h+2,\dots,q\) possono lasciare la stessa capacità residua, e quindi lo stesso valore \(v(h,k)\) può servire più volte durante la valutazione ricorsiva della formula \(\eqref{eq:mckp}\).

    \(\rightsquigarrow\) Sottoproblemi sovrapposti verificati!

  • Il valore \(v(h,k)\) dipende solo dai valori \(v(h-1,k')\) con \(k'< k\). Quindi l'approccio bottom-up calcola le righe \(h=0,1,\dots,q\) in quest'ordine, ciascuna per \(k\) crescente, e memorizza ogni valore in una tabella di lookup.

  • Il valore ottimo dell'istanza dell'MCKP è \(v(q,c)\), e l'istanza è inammissibile se e solo se \(v(q,c)=-\infty\).

• Passo 2: calcolo di una soluzione ottima

  • Per ogni classe \(h\) e capacità \(k\), memorizziamo \(s[h][k]\), l'oggetto della classe \(h\) scelto in una soluzione ottima della sottoistanza \((h,k)\), cioè l'oggetto che massimizza il membro destro della formula \(\eqref{eq:mckp}\).

  • Se \(v[h][k]=-\infty\), non si sceglie alcun oggetto e \(s[h][k]=0\).

  Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up, che memorizza la matrice \(s\) insieme alla matrice \(v\):

  Algoritmo: MCKP_DP

  Input: Un'istanza dell'MCKP data da \(q\), dalle classi \(\mathscr{J}_1,\dots,\mathscr{J}_q\), dai vettori \(p[1..n]\), \(w[1..n]\) e dalla capacità \(c\)

  Output: Il valore ottimo dell'istanza dell'MCKP e la matrice \(s[0..q][0..c]\)

  1Function MCKP_DP(\(q,\mathscr{J},p,w,c\))

  2\(v := \textnormal{new array}[0..q][0..c]\); \(s := \textnormal{new array}[0..q][0..c]\)

  3for \(k := 0\) to \(c\) do

  4\(v[0][k] \leftarrow 0\); \(s[0][k] \leftarrow 0\)

  5end

  6for \(h := 1\) to \(q\) do

  7for \(k := 0\) to \(c\) do

  8\(m := -\infty\); \(t := 0\)

  9for each \(j \in \mathscr{J}_h\) do

  10if \(w[j]\le k\) e \(p[j]+v[h-1][k-w[j]] > m\) then

  11\(m \leftarrow p[j]+v[h-1][k-w[j]]\); \(t \leftarrow j\)

  12end

  13end

  14\(v[h][k] \leftarrow m\); \(s[h][k] \leftarrow t\)

  15end

  16end

  17return \(v[q][c], s\)

  • La variabile \(m\) parte da \(-\infty\), non da \(0\): si deve scegliere esattamente un oggetto della classe \(h\), quindi il valore di una scelta vuota non è disponibile.

  • Il ciclo più interno prova ogni oggetto \(j\) della classe \(h\) che entra nello zaino, conserva in \(m\) il valore massimo trovato finora e in \(t\) l'oggetto che lo dà.

  • Se nessun oggetto della classe \(h\) dà un valore maggiore di \(-\infty\), la cella mantiene \(v[h][k]=-\infty\) e \(s[h][k]=0\).

  • In caso di pareggio si conserva l'oggetto incontrato per primo in \(\mathscr{J}_h\), perché \(m\) viene aggiornato solo quando il valore è strettamente maggiore.

  Esempio 21.2: Esecuzione dell'algoritmo di PD

  Consideriamo l'istanza dell'MCKP dell'Esempio 21.1, con capacità \(c=10\) e classi \(\mathscr{J}_1=\{1,2\}\), \(\mathscr{J}_2=\{3,4,5\}\), \(\mathscr{J}_3=\{6,7\}\).

  Per ogni passo dell'algoritmo di PD con \(h\ge 1\), la tabella riporta i valori di \(h\) e \(k\), le celle \(v[h][k]\) e \(s[h][k]\) e l'operazione eseguita. La riga \(h=0\) è \(v[0][k]=0\) e \(s[0][k]=0\) per ogni \(k\).

  \(h\)	\(k\)	\(v[h][k]\)	\(s[h][k]\)	Azione
  \(1\)	\(0\)	\(-\infty\)	\(0\)	nessun oggetto di \(\mathscr{J}_1\) entra: \(-\infty\)
  \(1\)	\(1\)	\(4\)	\(1\)	\(\max\{p_1{+}v[0][0]\}=\max\{4\}=4\)
  \(1\)	\(2\)	\(4\)	\(1\)	\(\max\{p_1{+}v[0][1]\}=\max\{4\}=4\)
  \(1\)	\(3\)	\(4\)	\(1\)	\(\max\{p_1{+}v[0][2]\}=\max\{4\}=4\)
  \(1\)	\(4\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][3],\,p_2{+}v[0][0]\}=\max\{4,8\}=8\)
  \(1\)	\(5\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][4],\,p_2{+}v[0][1]\}=\max\{4,8\}=8\)
  \(1\)	\(6\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][5],\,p_2{+}v[0][2]\}=\max\{4,8\}=8\)
  \(1\)	\(7\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][6],\,p_2{+}v[0][3]\}=\max\{4,8\}=8\)
  \(1\)	\(8\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][7],\,p_2{+}v[0][4]\}=\max\{4,8\}=8\)
  \(1\)	\(9\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][8],\,p_2{+}v[0][5]\}=\max\{4,8\}=8\)
  \(1\)	\(10\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][9],\,p_2{+}v[0][6]\}=\max\{4,8\}=8\)
  \(2\)	\(0\)	\(-\infty\)	\(0\)	nessun oggetto di \(\mathscr{J}_2\) entra: \(-\infty\)
  \(2\)	\(1\)	\(-\infty\)	\(0\)	\(\max\{p_3{+}v[1][0]\}=\max\{-\infty\}=-\infty\)
  \(2\)	\(2\)	\(7\)	\(3\)	\(\max\{p_3{+}v[1][1],\,p_4{+}v[1][0]\}=\max\{7,-\infty\}=7\)
  \(2\)	\(3\)	\(9\)	\(4\)	\(\max\{p_3{+}v[1][2],\,p_4{+}v[1][1]\}=\max\{7,9\}=9\)
  \(2\)	\(4\)	\(9\)	\(4\)	\(\max\{p_3{+}v[1][3],\,p_4{+}v[1][2]\}=\max\{7,9\}=9\)
  \(2\)	\(5\)	\(11\)	\(3\)	\(\max\{p_3{+}v[1][4],\,p_4{+}v[1][3],\,p_5{+}v[1][0]\}=\max\{11,9,-\infty\}=11\)
  \(2\)	\(6\)	\(13\)	\(4\)	\(\max\{p_3{+}v[1][5],\,p_4{+}v[1][4],\,p_5{+}v[1][1]\}=\max\{11,13,11\}=13\)
  \(2\)	\(7\)	\(13\)	\(4\)	\(\max\{p_3{+}v[1][6],\,p_4{+}v[1][5],\,p_5{+}v[1][2]\}=\max\{11,13,11\}=13\)
  \(2\)	\(8\)	\(13\)	\(4\)	\(\max\{p_3{+}v[1][7],\,p_4{+}v[1][6],\,p_5{+}v[1][3]\}=\max\{11,13,11\}=13\)
  \(2\)	\(9\)	\(15\)	\(5\)	\(\max\{p_3{+}v[1][8],\,p_4{+}v[1][7],\,p_5{+}v[1][4]\}=\max\{11,13,15\}=15\)
  \(2\)	\(10\)	\(15\)	\(5\)	\(\max\{p_3{+}v[1][9],\,p_4{+}v[1][8],\,p_5{+}v[1][5]\}=\max\{11,13,15\}=15\)

  \(h\)	\(k\)	\(v[h][k]\)	\(s[h][k]\)	Azione
  \(3\)	\(0\)	\(-\infty\)	\(0\)	nessun oggetto di \(\mathscr{J}_3\) entra: \(-\infty\)
  \(3\)	\(1\)	\(-\infty\)	\(0\)	nessun oggetto di \(\mathscr{J}_3\) entra: \(-\infty\)
  \(3\)	\(2\)	\(-\infty\)	\(0\)	\(\max\{p_6{+}v[2][0]\}=\max\{-\infty\}=-\infty\)
  \(3\)	\(3\)	\(-\infty\)	\(0\)	\(\max\{p_6{+}v[2][1],\,p_7{+}v[2][0]\}=\max\{-\infty,-\infty\}=-\infty\)
  \(3\)	\(4\)	\(10\)	\(6\)	\(\max\{p_6{+}v[2][2],\,p_7{+}v[2][1]\}=\max\{10,-\infty\}=10\)
  \(3\)	\(5\)	\(14\)	\(7\)	\(\max\{p_6{+}v[2][3],\,p_7{+}v[2][2]\}=\max\{12,14\}=14\)
  \(3\)	\(6\)	\(16\)	\(7\)	\(\max\{p_6{+}v[2][4],\,p_7{+}v[2][3]\}=\max\{12,16\}=16\)
  \(3\)	\(7\)	\(16\)	\(7\)	\(\max\{p_6{+}v[2][5],\,p_7{+}v[2][4]\}=\max\{14,16\}=16\)
  \(3\)	\(8\)	\(18\)	\(7\)	\(\max\{p_6{+}v[2][6],\,p_7{+}v[2][5]\}=\max\{16,18\}=18\)
  \(3\)	\(9\)	\(20\)	\(7\)	\(\max\{p_6{+}v[2][7],\,p_7{+}v[2][6]\}=\max\{16,20\}=20\)
  \(3\)	\(10\)	\(20\)	\(7\)	\(\max\{p_6{+}v[2][8],\,p_7{+}v[2][7]\}=\max\{16,20\}=20\)

  Questa è la matrice \(v\) dopo l'esecuzione dell'algoritmo di PD:

  \[ \begin{array}{l|rrrrrrrrrrr} \hline {v[h][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {h=0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {h=1} & {-\infty} & {4} & {4} & {4} & {8} & {8} & {8} & {8} & {8} & {8} & {8} \\ {h=2} & {-\infty} & {-\infty} & {7} & {9} & {9} & {11} & {13} & {13} & {13} & {15} & {15} \\ {h=3} & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {10} & {14} & {16} & {16} & {18} & {20} & {20} \\ \hline \end{array} \]

  Questa è la matrice \(s\) dopo l'esecuzione dell'algoritmo di PD:

  \[ \begin{array}{l|rrrrrrrrrrr} \hline {s[h][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {h=0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {h=1} & {0} & {1} & {1} & {1} & {2} & {2} & {2} & {2} & {2} & {2} & {2} \\ {h=2} & {0} & {0} & {3} & {4} & {4} & {3} & {4} & {4} & {4} & {5} & {5} \\ {h=3} & {0} & {0} & {0} & {0} & {6} & {7} & {7} & {7} & {7} & {7} & {7} \\ \hline \end{array} \]

  Per esempio, \(v[2][1]=-\infty\): ogni scelta di un oggetto in \(\mathscr{J}_1\) e di uno in \(\mathscr{J}_2\) pesa almeno \(w_1+w_3=2\). Il valore ottimo dell'istanza è \(v[3][10]=20\), raggiunto con l'oggetto \(s[3][10]=7\) della classe \(3\).

  • Calcolata la matrice \(s\), se \(v[q][c]>-\infty\) si ricostruisce una soluzione ottima scorrendo le classi da \(h=q\) fino a \(h=1\), partendo da \(k=c\) e da \(x_j=0\) per ogni oggetto \(j\):

    \[ j \leftarrow s[h][k], \qquad x_j \leftarrow 1, \qquad k \leftarrow k - w_j. \]

  • Ogni classe dà esattamente un oggetto, quindi la ricostruzione seleziona \(q\) oggetti.

  Algoritmo: MCKP_Reconstruct

  Input: Il numero \(q\) di classi, la capacità \(c\), il vettore \(w[1..n]\) e la matrice \(s[0..q][0..c]\), con \(v[q][c]>-\infty\)

  Output: Una soluzione ottima dell'istanza dell'MCKP, come vettore binario

  1Function MCKP_Reconstruct(\(q,c,w,s\))

  2\(x := \textnormal{new array}[1..n]\), con \(x[j]=0\) per ogni \(j\)

  3\(k := c\)

  4for \(h := q\) downto \(1\) do

  5\(j \leftarrow s[h][k]\); \(x[j] \leftarrow 1\)

  6\(k \leftarrow k-w[j]\)

  7end

  8return \(x\)

  Esempio 21.3: Calcolo di una soluzione ottima

  Dopo l'esecuzione dell'algoritmo di PD sull'istanza dell'Esempio 21.1, partiamo da \(h=3\) e \(k=10\):

  Iterazione	\(h\)	\(k\)	\(j=s[h][k]\)	Selezione	Capacità
  \(-\)	\(-\)	\(-\)	\(-\)	\(-\)	\(k=10\)
  \(1\)	\(3\)	\(10\)	\(7\)	\(x[7]\leftarrow 1\)	\(k\leftarrow 10-3=7\)
  \(2\)	\(2\)	\(7\)	\(4\)	\(x[4]\leftarrow 1\)	\(k\leftarrow 7-2=5\)
  \(3\)	\(1\)	\(5\)	\(2\)	\(x[2]\leftarrow 1\)	\(k\leftarrow 5-4=1\)

  Una soluzione ottima dell'istanza dell'MCKP dell'Esempio 21.1 è \(S=\{2,4,7\}\), cioè il vettore \(x=(0,1,0,1,0,0,1)\). Il suo peso totale è \(4+2+3=9\le c\) e il suo valore ottimo è \(v(3,10)=20\).

21.1.1 Numero di passi

• Indichiamo con \(S(n,q,c)\) il numero di passi eseguiti da MCKP_DP nel caso peggiore. Il ciclo più interno scorre gli oggetti della classe \(h\), quindi su tutte le classi viene eseguito \(|\mathscr{J}_1|+|\mathscr{J}_2|+\dots+|\mathscr{J}_q|=n\) volte per ogni capacità \(k\). Supponendo che la condizione alla riga 10 sia sempre vera:

  • Le righe 2 e 17 vengono eseguite \(1\) volta ciascuna.

  • Le righe 3 e 4 vengono eseguite \(c+1\) volte ciascuna.

  • La riga 6 viene eseguita \(q\) volte.

  • Le righe 7, 8 e 14 vengono eseguite \(q(c+1)\) volte ciascuna.

  • Le righe 9, 10 e 11 vengono eseguite \(n(c+1)\) volte ciascuna.

• Quindi il numero totale di passi nel caso peggiore è

  \[ S(n,q,c)=3n(c+1)+3q(c+1)+q+2c+4. \]

  Poiché ogni classe contiene almeno un oggetto, \(1\le q\le n\), e

  \[ 3n(c+1)\;\le\; S(n,q,c)\;\le\; 6n(c+1)+n+2c+4. \]

  Entrambi i bound sono \(\Theta(nc)\), quindi \(S(n,q,c)=\Theta(nc)\).

  L'algoritmo di PD per l'MCKP esegue

  \[ S(n,q,c)=\Theta\big(c\,(|\mathscr{J}_1|+|\mathscr{J}_2|+\dots+|\mathscr{J}_q|)\big)=\Theta(nc) \]

  passi nel caso peggiore.

• La ricostruzione esegue \(\Theta(q)\) passi, uno per ogni classe.

21.2 Errori tipici

Attenzione

• Far partire \(m\) da \(0\) invece che da \(-\infty\). Con \(m=0\) una classe senza oggetti che entrano nello zaino verrebbe saltata, e la soluzione non conterrebbe esattamente un oggetto per classe.

• Aggiungere l'opzione «nessun oggetto della classe \(h\)». Il termine \(v(h-1,k)\) della ricorrenza del KP qui non ha posto: ogni classe dà esattamente un oggetto.

• Porre \(v(0,k)=-\infty\) per \(k\ge 1\). Senza classi il sottoinsieme vuoto è ammissibile per ogni capacità: la capacità non deve essere riempita.

• Ricostruire un'istanza inammissibile. Se \(v(q,c)=-\infty\) l'istanza non ha soluzioni ammissibili, e \(s[q][c]=0\) non dà alcun oggetto da selezionare.

21.3 In sintesi

In sintesi

• Gli stadi dell'algoritmo di PD sono le classi: \(v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}\), con \(v(0,k)=0\).

• Il valore \(-\infty\) segnala le sottoistanze senza soluzione ammissibile, e l'istanza è inammissibile se e solo se \(v(q,c)=-\infty\).

• La matrice \(s\) memorizza l'oggetto scelto in ogni classe, e una soluzione ottima si legge all'indietro a partire da \((q,c)\), un oggetto per classe.

• L'algoritmo di PD esegue \(\Theta(c\sum_{h=1}^{q}|\mathscr{J}_h|)=\Theta(nc)\) passi.

Quadro riassuntivo dell'esempio dell'MCKP. Esempio 21.1 (\(c=10\), tre classi):

Metodo	Lower bound	Upper bound	Origine
Algoritmo di PD	\(20\)	\(20\)	valore ottimo, soluzione \(S=\{2,4,7\}\)

---

Esercizi su questo capitolo: Zaino a scelta multipla (MCKP)