Esercizi · PD per il problema dello zaino con setup¶

Esercizi · Capitolo 23 · ogni soluzione si apre con un clic · Capitolo 23: Zaino con setup (KPS) · Eserciziario, volume 3 (PDF)

Ricorrenza usata in questi esercizi

L'algoritmo di PD del capitolo «PD per il problema dello zaino con setup». Gli oggetti sono numerati classe per classe, $\mathscr{J}_h=\{\ell_{h-1}+1,\dots,\ell_h\}$, $t_h=|\mathscr{J}_h|$, e $j=\ell_{h-1}+i$ è l'$i$-esimo oggetto della classe $h$:

\[ u(h,i,k)= \left\{ \begin{array}{ll} -\infty & \textrm{se $i=0$ e $k<s_h$,}\\[2ex] v(h-1,k-s_h)-f_h & \textrm{se $i=0$ e $k\ge s_h$,}\\[2ex] u(h,i-1,k) & \textrm{se $i\ge 1$ e $w_j>k$,}\\[2ex] \begin{array}[t]{@{}l@{}}\displaystyle \max \bigg\{ u(h,i-1,k),\\ \qquad p_j+u(h,i-1,k-w_j) \bigg\}\end{array} & \textrm{se $i\ge 1$ e $w_j\le k$,} \end{array} \right. \]

\[ v(h,k)= \left\{ \begin{array}{ll} 0 & \textrm{se $h=0$,}\\[2ex] \max \big\{ v(h-1,k),\; u(h,t_h,k) \big\} & \textrm{se $h\ge 1$.} \end{array} \right. \]

Il valore ottimo è $v(q,c)$. Le tabelle delle scelte memorizzano $s[h][i][k]=1$ se l'$i$-esimo oggetto della classe $h$ è selezionato, e $o[h][k]=1$ se la classe $h$ è aperta. La ricostruzione scorre le classi a partire da $h=q$ e $k=c$: una classe aperta si scorre come nel KP, e poi $k$ diminuisce di $s_h$.

Esercizio 23.1: Esercizio 1: problema dello zaino con setup

Consideriamo la seguente istanza del KPS, con uno zaino di capacità $c=7$ e $4$ oggetti partizionati in $q=2$ classi: $\mathscr{J}_1=\{1,2\}$ con $f_1=2$ e $s_1=1$, $\mathscr{J}_2=\{3,4\}$ con $f_2=2$ e $s_2=1$. I ricavi e i pesi sono:

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

Domande

Eseguire l'algoritmo di PD bottom-up e scrivere la tabella di tutte le righe $v[h][\cdot]$ e $u[h][i][\cdot]$, nell'ordine di calcolo.
Scrivere le tabelle delle scelte $s$ e $o$, ricostruire una soluzione ottima $(x_1,x_2,x_3,x_4)$, dire quali classi sono aperte e riportare il valore ottimo.

Soluzione

La ricorrenza e le convenzioni sono quelle del box all'inizio di questi esercizi.

Per ogni classe $h$ l'algoritmo di PD calcola la riga di setup $u[h][0][\cdot]$, le righe degli oggetti della classe $h$ e la riga $v[h][\cdot]$. In caso di pareggio l'oggetto non viene selezionato e la classe resta chiusa. Questa è la tabella dopo l'esecuzione dell'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$
$v[0][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$u[1][0][k]$ (setup)	$-\infty$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$
$u[1][1][k]$ ($j=1$)	$-\infty$	$-2$	$-2$	$0$	$0$	$0$	$0$	$0$
$u[1][2][k]$ ($j=2$)	$-\infty$	$-2$	$7$	$7$	$9$	$9$	$9$	$9$
$v[1][k]$	$0$	$0$	$7$	$7$	$9$	$9$	$9$	$9$
$u[2][0][k]$ (setup)	$-\infty$	$-2$	$-2$	$5$	$5$	$7$	$7$	$7$
$u[2][1][k]$ ($j=3$)	$-\infty$	$-2$	$-2$	$5$	$5$	$8$	$8$	$10$
$u[2][2][k]$ ($j=4$)	$-\infty$	$-2$	$6$	$6$	$13$	$13$	$16$	$16$
$v[2][k]$	$0$	$0$	$7$	$7$	$13$	$13$	$16$	$16$

Questi sono i calcoli delle celle usate dalla ricostruzione, nell'ordine in cui essa le legge:

$v[2][7]=\max\{v[1][7],\,u[2][2][7]\}=\max\{9,\,16\}=16$
$u[2][2][7]=\max\{u[2][1][7],\,p_4+u[2][1][6]\}=\max\{10,\,16\}=16$
$u[2][1][6]=\max\{u[2][0][6],\,p_3+u[2][0][4]\}=\max\{7,\,8\}=8$
$u[2][0][4]=v[1][3]-f_2=7-2=5$
$v[1][3]=\max\{v[0][3],\,u[1][2][3]\}=\max\{0,\,7\}=7$
$u[1][2][3]=\max\{u[1][1][3],\,p_2+u[1][1][2]\}=\max\{0,\,7\}=7$
$u[1][1][2]=\max\{u[1][0][2],\,p_1+u[1][0][0]\}=\max\{-2,\,-\infty\}=-2$
$u[1][0][2]=v[0][1]-f_1=0-2=-2$

Queste sono le tabelle delle scelte calcolate dall'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$
$s[1][1][k]$ ($j=1$)	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$
$s[1][2][k]$ ($j=2$)	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$
$o[1][k]$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$
$s[2][1][k]$ ($j=3$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$
$s[2][2][k]$ ($j=4$)	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$
$o[2][k]$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$

Partendo da $h=2$ e $k=7$:

Iterazione	Stadio	$k$	Scelta	$x[2]$	$x[3]$	$x[4]$	Azione
$-$	$-$	$-$	$-$	0	0	0	$k=7$
$1$	$h=2$	$7$	$o[2][7]=1$	0	0	0	classe $2$ aperta
$2$	$j=4$	$7$	$s[2][2][7]=1$	0	0	1	$k\leftarrow 7-1=6$
$3$	$j=3$	$6$	$s[2][1][6]=1$	0	1	1	$k\leftarrow 6-2=4$
$-$	$-$	$4$	$-$	0	1	1	setup: $k\leftarrow 4-s_2=3$
$4$	$h=1$	$3$	$o[1][3]=1$	0	1	1	classe $1$ aperta
$5$	$j=2$	$3$	$s[1][2][3]=1$	1	1	1	$k\leftarrow 3-1=2$
$6$	$j=1$	$2$	$s[1][1][2]=0$	1	1	1	$k=2$
$-$	$-$	$2$	$-$	1	1	1	setup: $k\leftarrow 2-s_1=1$

Il vettore $(0,1,1,1)$ è una soluzione ottima: entrambe le classi sono aperte, e sono selezionati gli oggetti $\{2,3,4\}$. Il suo peso totale è $1+2+1+s_1+s_2=6\le c$, e il valore ottimo è $v[2][7]=9+3+8-f_1-f_2=16$.

Esercizio 23.2: Esercizio 2: problema dello zaino con setup

Consideriamo la seguente istanza del KPS, con uno zaino di capacità $c=7$ e $4$ oggetti partizionati in $q=2$ classi: $\mathscr{J}_1=\{1,2\}$ con $f_1=4$ e $s_1=2$, $\mathscr{J}_2=\{3,4\}$ con $f_2=4$ e $s_2=1$. I ricavi e i pesi sono:

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

Domande

Eseguire l'algoritmo di PD bottom-up e scrivere la tabella di tutte le righe $v[h][\cdot]$ e $u[h][i][\cdot]$, nell'ordine di calcolo.
Scrivere le tabelle delle scelte $s$ e $o$, ricostruire una soluzione ottima $(x_1,x_2,x_3,x_4)$, dire quali classi sono aperte e riportare il valore ottimo.

Soluzione

La ricorrenza e le convenzioni sono quelle del box all'inizio di questi esercizi.

Per ogni classe $h$ l'algoritmo di PD calcola la riga di setup $u[h][0][\cdot]$, le righe degli oggetti della classe $h$ e la riga $v[h][\cdot]$. In caso di pareggio l'oggetto non viene selezionato e la classe resta chiusa. Questa è la tabella dopo l'esecuzione dell'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$
$v[0][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$u[1][0][k]$ (setup)	$-\infty$	$-\infty$	$-4$	$-4$	$-4$	$-4$	$-4$	$-4$
$u[1][1][k]$ ($j=1$)	$-\infty$	$-\infty$	$-4$	$-4$	$-4$	$3$	$3$	$3$
$u[1][2][k]$ ($j=2$)	$-\infty$	$-\infty$	$-4$	$-4$	$-4$	$3$	$3$	$3$
$v[1][k]$	$0$	$0$	$0$	$0$	$0$	$3$	$3$	$3$
$u[2][0][k]$ (setup)	$-\infty$	$-4$	$-4$	$-4$	$-4$	$-4$	$-1$	$-1$
$u[2][1][k]$ ($j=3$)	$-\infty$	$-4$	$-4$	$-4$	$5$	$5$	$5$	$5$
$u[2][2][k]$ ($j=4$)	$-\infty$	$-4$	$-4$	$-4$	$5$	$5$	$5$	$7$
$v[2][k]$	$0$	$0$	$0$	$0$	$5$	$5$	$5$	$7$

Questi sono i calcoli delle celle usate dalla ricostruzione, nell'ordine in cui essa le legge:

$v[2][7]=\max\{v[1][7],\,u[2][2][7]\}=\max\{3,\,7\}=7$
$u[2][2][7]=\max\{u[2][1][7],\,p_4+u[2][1][4]\}=\max\{5,\,7\}=7$
$u[2][1][4]=\max\{u[2][0][4],\,p_3+u[2][0][1]\}=\max\{-4,\,5\}=5$
$u[2][0][1]=v[1][0]-f_2=0-4=-4$
$v[1][0]=\max\{v[0][0],\,u[1][2][0]\}=\max\{0,\,-\infty\}=0$

Queste sono le tabelle delle scelte calcolate dall'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$
$s[1][1][k]$ ($j=1$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$
$s[1][2][k]$ ($j=2$)	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$o[1][k]$	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$
$s[2][1][k]$ ($j=3$)	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$
$s[2][2][k]$ ($j=4$)	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$1$
$o[2][k]$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$

Partendo da $h=2$ e $k=7$:

Iterazione	Stadio	$k$	Scelta	$x[3]$	$x[4]$	Azione
$-$	$-$	$-$	$-$	0	0	$k=7$
$1$	$h=2$	$7$	$o[2][7]=1$	0	0	classe $2$ aperta
$2$	$j=4$	$7$	$s[2][2][7]=1$	0	1	$k\leftarrow 7-3=4$
$3$	$j=3$	$4$	$s[2][1][4]=1$	1	1	$k\leftarrow 4-3=1$
$-$	$-$	$1$	$-$	1	1	setup: $k\leftarrow 1-s_2=0$
$4$	$h=1$	$0$	$o[1][0]=0$	1	1	classe $1$ chiusa

Il vettore $(0,0,1,1)$ è una soluzione ottima: solo la classe $2$ è aperta, e sono selezionati gli oggetti $\{3,4\}$. Il suo peso totale è $3+3+s_2=7\le c$, e il valore ottimo è $v[2][7]=9+2-f_2=7$.

Esercizio 23.3: Esercizio 3: problema dello zaino con setup

Consideriamo la seguente istanza del KPS, con uno zaino di capacità $c=8$ e $5$ oggetti partizionati in $q=2$ classi: $\mathscr{J}_1=\{1,2\}$ con $f_1=1$ e $s_1=1$, $\mathscr{J}_2=\{3,4,5\}$ con $f_2=2$ e $s_2=2$. I ricavi e i pesi sono:

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

Domande

Eseguire l'algoritmo di PD bottom-up e scrivere la tabella di tutte le righe $v[h][\cdot]$ e $u[h][i][\cdot]$, nell'ordine di calcolo.
Scrivere le tabelle delle scelte $s$ e $o$, ricostruire una soluzione ottima $(x_1,x_2,x_3,x_4,x_5)$, dire quali classi sono aperte e riportare il valore ottimo.

Soluzione

La ricorrenza e le convenzioni sono quelle del box all'inizio di questi esercizi.

Per ogni classe $h$ l'algoritmo di PD calcola la riga di setup $u[h][0][\cdot]$, le righe degli oggetti della classe $h$ e la riga $v[h][\cdot]$. In caso di pareggio l'oggetto non viene selezionato e la classe resta chiusa. Questa è la tabella dopo l'esecuzione dell'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$
$v[0][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$u[1][0][k]$ (setup)	$-\infty$	$-1$	$-1$	$-1$	$-1$	$-1$	$-1$	$-1$	$-1$
$u[1][1][k]$ ($j=1$)	$-\infty$	$-1$	$-1$	$-1$	$-1$	$2$	$2$	$2$	$2$
$u[1][2][k]$ ($j=2$)	$-\infty$	$-1$	$8$	$8$	$8$	$8$	$11$	$11$	$11$
$v[1][k]$	$0$	$0$	$8$	$8$	$8$	$8$	$11$	$11$	$11$
$u[2][0][k]$ (setup)	$-\infty$	$-\infty$	$-2$	$-2$	$6$	$6$	$6$	$6$	$9$
$u[2][1][k]$ ($j=3$)	$-\infty$	$-\infty$	$-2$	$3$	$6$	$11$	$11$	$11$	$11$
$u[2][2][k]$ ($j=4$)	$-\infty$	$-\infty$	$-2$	$3$	$6$	$11$	$11$	$13$	$18$
$u[2][3][k]$ ($j=5$)	$-\infty$	$-\infty$	$-2$	$7$	$12$	$15$	$20$	$20$	$22$
$v[2][k]$	$0$	$0$	$8$	$8$	$12$	$15$	$20$	$20$	$22$

Questi sono i calcoli delle celle usate dalla ricostruzione, nell'ordine in cui essa le legge:

$v[2][8]=\max\{v[1][8],\,u[2][3][8]\}=\max\{11,\,22\}=22$
$u[2][3][8]=\max\{u[2][2][8],\,p_5+u[2][2][7]\}=\max\{18,\,22\}=22$
$u[2][2][7]=\max\{u[2][1][7],\,p_4+u[2][1][4]\}=\max\{11,\,13\}=13$
$u[2][1][4]=\max\{u[2][0][4],\,p_3+u[2][0][3]\}=\max\{6,\,3\}=6$
$u[2][0][4]=v[1][2]-f_2=8-2=6$
$v[1][2]=\max\{v[0][2],\,u[1][2][2]\}=\max\{0,\,8\}=8$
$u[1][2][2]=\max\{u[1][1][2],\,p_2+u[1][1][1]\}=\max\{-1,\,8\}=8$
$u[1][1][1]=u[1][0][1]=-1$, perché $w_1>1$
$u[1][0][1]=v[0][0]-f_1=0-1=-1$

Queste sono le tabelle delle scelte calcolate dall'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$
$s[1][1][k]$ ($j=1$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$
$s[1][2][k]$ ($j=2$)	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$o[1][k]$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[2][1][k]$ ($j=3$)	$0$	$0$	$0$	$1$	$0$	$1$	$1$	$1$	$1$
$s[2][2][k]$ ($j=4$)	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$1$	$1$
$s[2][3][k]$ ($j=5$)	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$
$o[2][k]$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$

Partendo da $h=2$ e $k=8$:

Iterazione	Stadio	$k$	Scelta	$x[2]$	$x[4]$	$x[5]$	Azione
$-$	$-$	$-$	$-$	0	0	0	$k=8$
$1$	$h=2$	$8$	$o[2][8]=1$	0	0	0	classe $2$ aperta
$2$	$j=5$	$8$	$s[2][3][8]=1$	0	0	1	$k\leftarrow 8-1=7$
$3$	$j=4$	$7$	$s[2][2][7]=1$	0	1	1	$k\leftarrow 7-3=4$
$4$	$j=3$	$4$	$s[2][1][4]=0$	0	1	1	$k=4$
$-$	$-$	$4$	$-$	0	1	1	setup: $k\leftarrow 4-s_2=2$
$5$	$h=1$	$2$	$o[1][2]=1$	0	1	1	classe $1$ aperta
$6$	$j=2$	$2$	$s[1][2][2]=1$	1	1	1	$k\leftarrow 2-1=1$
$7$	$j=1$	$1$	$s[1][1][1]=0$	1	1	1	$k=1$
$-$	$-$	$1$	$-$	1	1	1	setup: $k\leftarrow 1-s_1=0$

Il vettore $(0,1,0,1,1)$ è una soluzione ottima: entrambe le classi sono aperte, e sono selezionati gli oggetti $\{2,4,5\}$. Il suo peso totale è $1+3+1+s_1+s_2=8\le c$, e il valore ottimo è $v[2][8]=9+7+9-f_1-f_2=22$.

Esercizio 23.4: Esercizio 4: problema dello zaino con setup

Consideriamo la seguente istanza del KPS, con uno zaino di capacità $c=8$ e $5$ oggetti partizionati in $q=2$ classi: $\mathscr{J}_1=\{1,2,3\}$ con $f_1=2$ e $s_1=1$, $\mathscr{J}_2=\{4,5\}$ con $f_2=1$ e $s_2=1$. I ricavi e i pesi sono:

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

Domande

Eseguire l'algoritmo di PD bottom-up e scrivere la tabella di tutte le righe $v[h][\cdot]$ e $u[h][i][\cdot]$, nell'ordine di calcolo.
Scrivere le tabelle delle scelte $s$ e $o$, ricostruire una soluzione ottima $(x_1,x_2,x_3,x_4,x_5)$, dire quali classi sono aperte e riportare il valore ottimo.

Soluzione

La ricorrenza e le convenzioni sono quelle del box all'inizio di questi esercizi.

Per ogni classe $h$ l'algoritmo di PD calcola la riga di setup $u[h][0][\cdot]$, le righe degli oggetti della classe $h$ e la riga $v[h][\cdot]$. In caso di pareggio l'oggetto non viene selezionato e la classe resta chiusa. Questa è la tabella dopo l'esecuzione dell'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$
$v[0][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$u[1][0][k]$ (setup)	$-\infty$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$
$u[1][1][k]$ ($j=1$)	$-\infty$	$-2$	$4$	$4$	$4$	$4$	$4$	$4$	$4$
$u[1][2][k]$ ($j=2$)	$-\infty$	$-2$	$7$	$13$	$13$	$13$	$13$	$13$	$13$
$u[1][3][k]$ ($j=3$)	$-\infty$	$-2$	$7$	$13$	$13$	$13$	$16$	$22$	$22$
$v[1][k]$	$0$	$0$	$7$	$13$	$13$	$13$	$16$	$22$	$22$
$u[2][0][k]$ (setup)	$-\infty$	$-1$	$-1$	$6$	$12$	$12$	$12$	$15$	$21$
$u[2][1][k]$ ($j=4$)	$-\infty$	$-1$	$-1$	$6$	$12$	$12$	$13$	$19$	$21$
$u[2][2][k]$ ($j=5$)	$-\infty$	$-1$	$-1$	$6$	$12$	$12$	$13$	$19$	$21$
$v[2][k]$	$0$	$0$	$7$	$13$	$13$	$13$	$16$	$22$	$22$

Questi sono i calcoli delle celle usate dalla ricostruzione, nell'ordine in cui essa le legge:

$v[2][8]=\max\{v[1][8],\,u[2][2][8]\}=\max\{22,\,21\}=22$
$v[1][8]=\max\{v[0][8],\,u[1][3][8]\}=\max\{0,\,22\}=22$
$u[1][3][8]=\max\{u[1][2][8],\,p_3+u[1][2][4]\}=\max\{13,\,22\}=22$
$u[1][2][4]=\max\{u[1][1][4],\,p_2+u[1][1][3]\}=\max\{4,\,13\}=13$
$u[1][1][3]=\max\{u[1][0][3],\,p_1+u[1][0][2]\}=\max\{-2,\,4\}=4$
$u[1][0][2]=v[0][1]-f_1=0-2=-2$

Queste sono le tabelle delle scelte calcolate dall'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$
$s[1][1][k]$ ($j=1$)	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[1][2][k]$ ($j=2$)	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[1][3][k]$ ($j=3$)	$0$	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$
$o[1][k]$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[2][1][k]$ ($j=4$)	$0$	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$0$
$s[2][2][k]$ ($j=5$)	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$o[2][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$

Partendo da $h=2$ e $k=8$:

Iterazione	Stadio	$k$	Scelta	$x[1]$	$x[2]$	$x[3]$	Azione
$-$	$-$	$-$	$-$	0	0	0	$k=8$
$1$	$h=2$	$8$	$o[2][8]=0$	0	0	0	classe $2$ chiusa
$2$	$h=1$	$8$	$o[1][8]=1$	0	0	0	classe $1$ aperta
$3$	$j=3$	$8$	$s[1][3][8]=1$	0	0	1	$k\leftarrow 8-4=4$
$4$	$j=2$	$4$	$s[1][2][4]=1$	0	1	1	$k\leftarrow 4-1=3$
$5$	$j=1$	$3$	$s[1][1][3]=1$	1	1	1	$k\leftarrow 3-1=2$
$-$	$-$	$2$	$-$	1	1	1	setup: $k\leftarrow 2-s_1=1$

Il vettore $(1,1,1,0,0)$ è una soluzione ottima: solo la classe $1$ è aperta, e sono selezionati gli oggetti $\{1,2,3\}$. Il suo peso totale è $1+1+4+s_1=7\le c$, e il valore ottimo è $v[2][8]=6+9+9-f_1=22$.

Esercizio 23.5: Esercizio 5: problema dello zaino con setup

Consideriamo la seguente istanza del KPS, con uno zaino di capacità $c=9$ e $5$ oggetti partizionati in $q=2$ classi: $\mathscr{J}_1=\{1,2\}$ con $f_1=3$ e $s_1=2$, $\mathscr{J}_2=\{3,4,5\}$ con $f_2=2$ e $s_2=2$. I ricavi e i pesi sono:

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

Domande

Eseguire l'algoritmo di PD bottom-up e scrivere la tabella di tutte le righe $v[h][\cdot]$ e $u[h][i][\cdot]$, nell'ordine di calcolo.
Scrivere le tabelle delle scelte $s$ e $o$, ricostruire una soluzione ottima $(x_1,x_2,x_3,x_4,x_5)$, dire quali classi sono aperte e riportare il valore ottimo.

Soluzione

La ricorrenza e le convenzioni sono quelle del box all'inizio di questi esercizi.

Per ogni classe $h$ l'algoritmo di PD calcola la riga di setup $u[h][0][\cdot]$, le righe degli oggetti della classe $h$ e la riga $v[h][\cdot]$. In caso di pareggio l'oggetto non viene selezionato e la classe resta chiusa. Questa è la tabella dopo l'esecuzione dell'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$	$k=9$
$v[0][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$u[1][0][k]$ (setup)	$-\infty$	$-\infty$	$-3$	$-3$	$-3$	$-3$	$-3$	$-3$	$-3$	$-3$
$u[1][1][k]$ ($j=1$)	$-\infty$	$-\infty$	$-3$	$-3$	$-3$	$3$	$3$	$3$	$3$	$3$
$u[1][2][k]$ ($j=2$)	$-\infty$	$-\infty$	$-3$	$2$	$2$	$3$	$8$	$8$	$8$	$8$
$v[1][k]$	$0$	$0$	$0$	$2$	$2$	$3$	$8$	$8$	$8$	$8$
$u[2][0][k]$ (setup)	$-\infty$	$-\infty$	$-2$	$-2$	$-2$	$0$	$0$	$1$	$6$	$6$
$u[2][1][k]$ ($j=3$)	$-\infty$	$-\infty$	$-2$	$6$	$6$	$6$	$8$	$8$	$9$	$14$
$u[2][2][k]$ ($j=4$)	$-\infty$	$-\infty$	$-2$	$6$	$6$	$6$	$8$	$12$	$12$	$14$
$u[2][3][k]$ ($j=5$)	$-\infty$	$-\infty$	$-2$	$6$	$6$	$6$	$11$	$12$	$12$	$14$
$v[2][k]$	$0$	$0$	$0$	$6$	$6$	$6$	$11$	$12$	$12$	$14$

Questi sono i calcoli delle celle usate dalla ricostruzione, nell'ordine in cui essa le legge:

$v[2][9]=\max\{v[1][9],\,u[2][3][9]\}=\max\{8,\,14\}=14$
$u[2][3][9]=\max\{u[2][2][9],\,p_5+u[2][2][6]\}=\max\{14,\,13\}=14$
$u[2][2][9]=\max\{u[2][1][9],\,p_4+u[2][1][5]\}=\max\{14,\,12\}=14$
$u[2][1][9]=\max\{u[2][0][9],\,p_3+u[2][0][8]\}=\max\{6,\,14\}=14$
$u[2][0][8]=v[1][6]-f_2=8-2=6$
$v[1][6]=\max\{v[0][6],\,u[1][2][6]\}=\max\{0,\,8\}=8$
$u[1][2][6]=\max\{u[1][1][6],\,p_2+u[1][1][5]\}=\max\{3,\,8\}=8$
$u[1][1][5]=\max\{u[1][0][5],\,p_1+u[1][0][2]\}=\max\{-3,\,3\}=3$
$u[1][0][2]=v[0][0]-f_1=0-3=-3$

Queste sono le tabelle delle scelte calcolate dall'algoritmo di PD:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$	$k=9$
$s[1][1][k]$ ($j=1$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$
$s[1][2][k]$ ($j=2$)	$0$	$0$	$0$	$1$	$1$	$0$	$1$	$1$	$1$	$1$
$o[1][k]$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[2][1][k]$ ($j=3$)	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[2][2][k]$ ($j=4$)	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$0$
$s[2][3][k]$ ($j=5$)	$0$	$0$	$0$	$0$	$0$	$0$	$1$	$0$	$0$	$0$
$o[2][k]$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$

Partendo da $h=2$ e $k=9$:

Iterazione	Stadio	$k$	Scelta	$x[1]$	$x[2]$	$x[3]$	Azione
$-$	$-$	$-$	$-$	0	0	0	$k=9$
$1$	$h=2$	$9$	$o[2][9]=1$	0	0	0	classe $2$ aperta
$2$	$j=5$	$9$	$s[2][3][9]=0$	0	0	0	$k=9$
$3$	$j=4$	$9$	$s[2][2][9]=0$	0	0	0	$k=9$
$4$	$j=3$	$9$	$s[2][1][9]=1$	0	0	1	$k\leftarrow 9-1=8$
$-$	$-$	$8$	$-$	0	0	1	setup: $k\leftarrow 8-s_2=6$
$5$	$h=1$	$6$	$o[1][6]=1$	0	0	1	classe $1$ aperta
$6$	$j=2$	$6$	$s[1][2][6]=1$	0	1	1	$k\leftarrow 6-1=5$
$7$	$j=1$	$5$	$s[1][1][5]=1$	1	1	1	$k\leftarrow 5-3=2$
$-$	$-$	$2$	$-$	1	1	1	setup: $k\leftarrow 2-s_1=0$

Il vettore $(1,1,1,0,0)$ è una soluzione ottima: entrambe le classi sono aperte, e sono selezionati gli oggetti $\{1,2,3\}$. Il suo peso totale è $3+1+1+s_1+s_2=9\le c$, e il valore ottimo è $v[2][9]=6+5+8-f_1-f_2=14$.

Riga	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)
\(v[0][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(u[1][0][k]\) (setup)	\(-\infty\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)
\(u[1][1][k]\) (\(j=1\))	\(-\infty\)	\(-2\)	\(-2\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(u[1][2][k]\) (\(j=2\))	\(-\infty\)	\(-2\)	\(7\)	\(7\)	\(9\)	\(9\)	\(9\)	\(9\)
\(v[1][k]\)	\(0\)	\(0\)	\(7\)	\(7\)	\(9\)	\(9\)	\(9\)	\(9\)
\(u[2][0][k]\) (setup)	\(-\infty\)	\(-2\)	\(-2\)	\(5\)	\(5\)	\(7\)	\(7\)	\(7\)
\(u[2][1][k]\) (\(j=3\))	\(-\infty\)	\(-2\)	\(-2\)	\(5\)	\(5\)	\(8\)	\(8\)	\(10\)
\(u[2][2][k]\) (\(j=4\))	\(-\infty\)	\(-2\)	\(6\)	\(6\)	\(13\)	\(13\)	\(16\)	\(16\)
\(v[2][k]\)	\(0\)	\(0\)	\(7\)	\(7\)	\(13\)	\(13\)	\(16\)	\(16\)

Riga	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)
\(s[1][1][k]\) (\(j=1\))	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(s[1][2][k]\) (\(j=2\))	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(o[1][k]\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(s[2][1][k]\) (\(j=3\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)
\(s[2][2][k]\) (\(j=4\))	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(o[2][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)

Iterazione	Stadio	\(k\)	Scelta	\(x[2]\)	\(x[3]\)	\(x[4]\)	Azione
\(-\)	\(-\)	\(-\)	\(-\)	0	0	0	\(k=7\)
\(1\)	\(h=2\)	\(7\)	\(o[2][7]=1\)	0	0	0	classe \(2\) aperta
\(2\)	\(j=4\)	\(7\)	\(s[2][2][7]=1\)	0	0	1	\(k\leftarrow 7-1=6\)
\(3\)	\(j=3\)	\(6\)	\(s[2][1][6]=1\)	0	1	1	\(k\leftarrow 6-2=4\)
\(-\)	\(-\)	\(4\)	\(-\)	0	1	1	setup: \(k\leftarrow 4-s_2=3\)
\(4\)	\(h=1\)	\(3\)	\(o[1][3]=1\)	0	1	1	classe \(1\) aperta
\(5\)	\(j=2\)	\(3\)	\(s[1][2][3]=1\)	1	1	1	\(k\leftarrow 3-1=2\)
\(6\)	\(j=1\)	\(2\)	\(s[1][1][2]=0\)	1	1	1	\(k=2\)
\(-\)	\(-\)	\(2\)	\(-\)	1	1	1	setup: \(k\leftarrow 2-s_1=1\)

Riga	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)
\(v[0][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(u[1][0][k]\) (setup)	\(-\infty\)	\(-\infty\)	\(-4\)	\(-4\)	\(-4\)	\(-4\)	\(-4\)	\(-4\)
\(u[1][1][k]\) (\(j=1\))	\(-\infty\)	\(-\infty\)	\(-4\)	\(-4\)	\(-4\)	\(3\)	\(3\)	\(3\)
\(u[1][2][k]\) (\(j=2\))	\(-\infty\)	\(-\infty\)	\(-4\)	\(-4\)	\(-4\)	\(3\)	\(3\)	\(3\)
\(v[1][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(3\)	\(3\)	\(3\)
\(u[2][0][k]\) (setup)	\(-\infty\)	\(-4\)	\(-4\)	\(-4\)	\(-4\)	\(-4\)	\(-1\)	\(-1\)
\(u[2][1][k]\) (\(j=3\))	\(-\infty\)	\(-4\)	\(-4\)	\(-4\)	\(5\)	\(5\)	\(5\)	\(5\)
\(u[2][2][k]\) (\(j=4\))	\(-\infty\)	\(-4\)	\(-4\)	\(-4\)	\(5\)	\(5\)	\(5\)	\(7\)
\(v[2][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(5\)	\(5\)	\(5\)	\(7\)

Riga	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)
\(s[1][1][k]\) (\(j=1\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)
\(s[1][2][k]\) (\(j=2\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(o[1][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)
\(s[2][1][k]\) (\(j=3\))	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)
\(s[2][2][k]\) (\(j=4\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)
\(o[2][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)