Esercizi · PD per il problema dello zaino limitato¶

Esercizi · Capitolo 19 · ogni soluzione si apre con un clic · Capitolo 19: Zaino limitato (BKP) · Eserciziario, volume 3 (PDF)

Esercizio 19.1: Esercizio 1: problema dello zaino limitato

Consideriamo la seguente istanza del BKP, in cui lo zaino ha capacità \(c=6\) e i profitti, i pesi e i limiti associati ai tipi di oggetto sono:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori delle matrici \(v\) e \(s\).
Usando la matrice \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo dell'algoritmo di PD bottom-up

Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(j\) e \(k\), le celle \(v[j][k]\) e \(s[j][k]\) e l'operazione eseguita.

\(j\)	\(k\)	\(v[j][k]\)	\(s[j][k]\)	Azione
0	0	0	0	\(v[0][0]\leftarrow 0\), \(s[0][0]\leftarrow 0\)
0	1	0	0	\(v[0][1]\leftarrow 0\), \(s[0][1]\leftarrow 0\)
0	2	0	0	\(v[0][2]\leftarrow 0\), \(s[0][2]\leftarrow 0\)
0	3	0	0	\(v[0][3]\leftarrow 0\), \(s[0][3]\leftarrow 0\)
0	4	0	0	\(v[0][4]\leftarrow 0\), \(s[0][4]\leftarrow 0\)
0	5	0	0	\(v[0][5]\leftarrow 0\), \(s[0][5]\leftarrow 0\)
0	6	0	0	\(v[0][6]\leftarrow 0\), \(s[0][6]\leftarrow 0\)
1	0	0	0	\(\max\{v[0][0]\}=0\)
1	1	0	0	\(\max\{v[0][1]\}=0\)
1	2	4	1	\(\max\{v[0][2],\,p[1]{+}v[0][0]\}=\max\{0,4\}=4\)
1	3	4	1	\(\max\{v[0][3],\,p[1]{+}v[0][1]\}=\max\{0,4\}=4\)
1	4	8	2	\(\max\{v[0][4],\,p[1]{+}v[0][2],\,2p[1]{+}v[0][0]\}=\max\{0,4,8\}=8\)
1	5	8	2	\(\max\{v[0][5],\,p[1]{+}v[0][3],\,2p[1]{+}v[0][1]\}=\max\{0,4,8\}=8\)
1	6	8	2	\(\max\{v[0][6],\,p[1]{+}v[0][4],\,2p[1]{+}v[0][2]\}=\max\{0,4,8\}=8\)
2	0	0	0	\(\max\{v[1][0]\}=0\)
2	1	0	0	\(\max\{v[1][1]\}=0\)
2	2	4	0	\(\max\{v[1][2]\}=4\)
2	3	5	1	\(\max\{v[1][3],\,p[2]{+}v[1][0]\}=\max\{4,5\}=5\)
2	4	8	0	\(\max\{v[1][4],\,p[2]{+}v[1][1]\}=\max\{8,5\}=8\)
2	5	9	1	\(\max\{v[1][5],\,p[2]{+}v[1][2]\}=\max\{8,9\}=9\)
2	6	9	1	\(\max\{v[1][6],\,p[2]{+}v[1][3]\}=\max\{8,9\}=9\)

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

\[ \begin{array}{l|rrrrrrr} \hline {v[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 4 & 4 & 8 & 8 & 8 \\ {j=2} & 0 & 0 & 4 & 5 & 8 & 9 & 9 \\ \hline \end{array} \]

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

\[ \begin{array}{l|rrrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 1 & 1 & 2 & 2 & 2 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \hline \end{array} \]

Abbiamo la seguente matrice \(s\):

\[ \begin{array}{l|rrrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 1 & 1 & 2 & 2 & 2 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ \hline \end{array} \]

Possiamo ricostruire una soluzione ottima partendo da \(j=2\) e \(k=6\) come segue:

Iterazione	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	Azione
-	-	-	-	0	0	\(k=6\)
1	2	6	1	0	1	\(x[2]\leftarrow 1\), \(k\leftarrow 6-1\cdot3=3\)
2	1	3	1	1	1	\(x[1]\leftarrow 1\), \(k\leftarrow 3-1\cdot2=1\)

Quindi il vettore

\[ (1,1) \]

è una soluzione ottima. Il valore ottimo è

\[ v[2][6]=9. \]

Esercizio 19.2: Esercizio 2: problema dello zaino limitato

Consideriamo la seguente istanza del BKP, in cui lo zaino ha capacità \(c=7\) e i profitti, i pesi e i limiti associati ai tipi di oggetto sono:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori delle matrici \(v\) e \(s\).
Usando la matrice \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo dell'algoritmo di PD bottom-up

Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(j\) e \(k\), le celle \(v[j][k]\) e \(s[j][k]\) e l'operazione eseguita.

\(j\)	\(k\)	\(v[j][k]\)	\(s[j][k]\)	Azione
0	0	0	0	\(v[0][0]\leftarrow 0\), \(s[0][0]\leftarrow 0\)
0	1	0	0	\(v[0][1]\leftarrow 0\), \(s[0][1]\leftarrow 0\)
0	2	0	0	\(v[0][2]\leftarrow 0\), \(s[0][2]\leftarrow 0\)
0	3	0	0	\(v[0][3]\leftarrow 0\), \(s[0][3]\leftarrow 0\)
0	4	0	0	\(v[0][4]\leftarrow 0\), \(s[0][4]\leftarrow 0\)
0	5	0	0	\(v[0][5]\leftarrow 0\), \(s[0][5]\leftarrow 0\)
0	6	0	0	\(v[0][6]\leftarrow 0\), \(s[0][6]\leftarrow 0\)
0	7	0	0	\(v[0][7]\leftarrow 0\), \(s[0][7]\leftarrow 0\)
1	0	0	0	\(\max\{v[0][0]\}=0\)
1	1	3	1	\(\max\{v[0][1],\,p[1]{+}v[0][0]\}=\max\{0,3\}=3\)
1	2	6	2	\(\max\{v[0][2],\,p[1]{+}v[0][1],\,2p[1]{+}v[0][0]\}=\max\{0,3,6\}=6\)
1	3	9	3	\(\max\{v[0][3],\,p[1]{+}v[0][2],\,2p[1]{+}v[0][1],\,3p[1]{+}v[0][0]\}=\max\{0,3,6,9\}=9\)
1	4	9	3	\(\max\{v[0][4],\,p[1]{+}v[0][3],\,2p[1]{+}v[0][2],\,3p[1]{+}v[0][1]\}=\max\{0,3,6,9\}=9\)
1	5	9	3	\(\max\{v[0][5],\,p[1]{+}v[0][4],\,2p[1]{+}v[0][3],\,3p[1]{+}v[0][2]\}=\max\{0,3,6,9\}=9\)
1	6	9	3	\(\max\{v[0][6],\,p[1]{+}v[0][5],\,2p[1]{+}v[0][4],\,3p[1]{+}v[0][3]\}=\max\{0,3,6,9\}=9\)
1	7	9	3	\(\max\{v[0][7],\,p[1]{+}v[0][6],\,2p[1]{+}v[0][5],\,3p[1]{+}v[0][4]\}=\max\{0,3,6,9\}=9\)
2	0	0	0	\(\max\{v[1][0]\}=0\)
2	1	3	0	\(\max\{v[1][1]\}=3\)
2	2	6	0	\(\max\{v[1][2]\}=6\)
2	3	9	0	\(\max\{v[1][3]\}=9\)
2	4	9	0	\(\max\{v[1][4],\,p[2]{+}v[1][0]\}=\max\{9,8\}=9\)
2	5	11	1	\(\max\{v[1][5],\,p[2]{+}v[1][1]\}=\max\{9,11\}=11\)
2	6	14	1	\(\max\{v[1][6],\,p[2]{+}v[1][2]\}=\max\{9,14\}=14\)
2	7	17	1	\(\max\{v[1][7],\,p[2]{+}v[1][3]\}=\max\{9,17\}=17\)

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

\[ \begin{array}{l|rrrrrrrr} \hline {v[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 3 & 6 & 9 & 9 & 9 & 9 & 9 \\ {j=2} & 0 & 3 & 6 & 9 & 9 & 11 & 14 & 17 \\ \hline \end{array} \]

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

\[ \begin{array}{l|rrrrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 2 & 3 & 3 & 3 & 3 & 3 \\ {j=2} & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline \end{array} \]

Abbiamo la seguente matrice \(s\):

\[ \begin{array}{l|rrrrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 2 & 3 & 3 & 3 & 3 & 3 \\ {j=2} & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline \end{array} \]

Possiamo ricostruire una soluzione ottima partendo da \(j=2\) e \(k=7\) come segue:

Iterazione	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	Azione
-	-	-	-	0	0	\(k=7\)
1	2	7	1	0	1	\(x[2]\leftarrow 1\), \(k\leftarrow 7-1\cdot4=3\)
2	1	3	3	3	1	\(x[1]\leftarrow 3\), \(k\leftarrow 3-3\cdot1=0\)

Quindi il vettore

\[ (3,1) \]

è una soluzione ottima. Il valore ottimo è

\[ v[2][7]=17. \]

Esercizio 19.3: Esercizio 3: problema dello zaino limitato

Consideriamo la seguente istanza del BKP, in cui lo zaino ha capacità \(c=5\) e i profitti, i pesi e i limiti associati ai tipi di oggetto sono:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori delle matrici \(v\) e \(s\).
Usando la matrice \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,x_3)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo dell'algoritmo di PD bottom-up

Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(j\) e \(k\), le celle \(v[j][k]\) e \(s[j][k]\) e l'operazione eseguita.

\(j\)	\(k\)	\(v[j][k]\)	\(s[j][k]\)	Azione
0	0	0	0	\(v[0][0]\leftarrow 0\), \(s[0][0]\leftarrow 0\)
0	1	0	0	\(v[0][1]\leftarrow 0\), \(s[0][1]\leftarrow 0\)
0	2	0	0	\(v[0][2]\leftarrow 0\), \(s[0][2]\leftarrow 0\)
0	3	0	0	\(v[0][3]\leftarrow 0\), \(s[0][3]\leftarrow 0\)
0	4	0	0	\(v[0][4]\leftarrow 0\), \(s[0][4]\leftarrow 0\)
0	5	0	0	\(v[0][5]\leftarrow 0\), \(s[0][5]\leftarrow 0\)
1	0	0	0	\(\max\{v[0][0]\}=0\)
1	1	2	1	\(\max\{v[0][1],\,p[1]{+}v[0][0]\}=\max\{0,2\}=2\)
1	2	2	1	\(\max\{v[0][2],\,p[1]{+}v[0][1]\}=\max\{0,2\}=2\)
1	3	2	1	\(\max\{v[0][3],\,p[1]{+}v[0][2]\}=\max\{0,2\}=2\)
1	4	2	1	\(\max\{v[0][4],\,p[1]{+}v[0][3]\}=\max\{0,2\}=2\)
1	5	2	1	\(\max\{v[0][5],\,p[1]{+}v[0][4]\}=\max\{0,2\}=2\)
2	0	0	0	\(\max\{v[1][0]\}=0\)
2	1	2	0	\(\max\{v[1][1]\}=2\)
2	2	3	1	\(\max\{v[1][2],\,p[2]{+}v[1][0]\}=\max\{2,3\}=3\)
2	3	5	1	\(\max\{v[1][3],\,p[2]{+}v[1][1]\}=\max\{2,5\}=5\)
2	4	5	1	\(\max\{v[1][4],\,p[2]{+}v[1][2]\}=\max\{2,5\}=5\)
2	5	5	1	\(\max\{v[1][5],\,p[2]{+}v[1][3]\}=\max\{2,5\}=5\)
3	0	0	0	\(\max\{v[2][0]\}=0\)
3	1	2	0	\(\max\{v[2][1]\}=2\)
3	2	3	0	\(\max\{v[2][2]\}=3\)
3	3	5	0	\(\max\{v[2][3],\,p[3]{+}v[2][0]\}=\max\{5,4\}=5\)
3	4	6	1	\(\max\{v[2][4],\,p[3]{+}v[2][1]\}=\max\{5,6\}=6\)
3	5	7	1	\(\max\{v[2][5],\,p[3]{+}v[2][2]\}=\max\{5,7\}=7\)

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

\[ \begin{array}{l|rrrrrr} \hline {v[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 2 & 2 & 2 & 2 & 2 \\ {j=2} & 0 & 2 & 3 & 5 & 5 & 5 \\ {j=3} & 0 & 2 & 3 & 5 & 6 & 7 \\ \hline \end{array} \]

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

\[ \begin{array}{l|rrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline \end{array} \]

Abbiamo la seguente matrice \(s\):

\[ \begin{array}{l|rrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline \end{array} \]

Possiamo ricostruire una soluzione ottima partendo da \(j=3\) e \(k=5\) come segue:

Iterazione	\(j\)	\(k\)	\(s[j][k]\)	\(x[2]\)	\(x[3]\)	Azione
-	-	-	-	0	0	\(k=5\)
1	3	5	1	0	1	\(x[3]\leftarrow 1\), \(k\leftarrow 5-1\cdot3=2\)
2	2	2	1	1	1	\(x[2]\leftarrow 1\), \(k\leftarrow 2-1\cdot2=0\)
3	1	0	0	1	1	\(x[1]\leftarrow 0\), \(k\leftarrow 0-0\cdot1=0\)

Quindi il vettore

\[ (0,1,1) \]

è una soluzione ottima. Il valore ottimo è

\[ v[3][5]=7. \]

Esercizio 19.4: Esercizio 4: problema dello zaino limitato

Consideriamo la seguente istanza del BKP, in cui lo zaino ha capacità \(c=8\) e i profitti, i pesi e i limiti associati ai tipi di oggetto sono:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori delle matrici \(v\) e \(s\).
Usando la matrice \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo dell'algoritmo di PD bottom-up

Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(j\) e \(k\), le celle \(v[j][k]\) e \(s[j][k]\) e l'operazione eseguita.

\(j\)	\(k\)	\(v[j][k]\)	\(s[j][k]\)	Azione
0	0	0	0	\(v[0][0]\leftarrow 0\), \(s[0][0]\leftarrow 0\)
0	1	0	0	\(v[0][1]\leftarrow 0\), \(s[0][1]\leftarrow 0\)
0	2	0	0	\(v[0][2]\leftarrow 0\), \(s[0][2]\leftarrow 0\)
0	3	0	0	\(v[0][3]\leftarrow 0\), \(s[0][3]\leftarrow 0\)
0	4	0	0	\(v[0][4]\leftarrow 0\), \(s[0][4]\leftarrow 0\)
0	5	0	0	\(v[0][5]\leftarrow 0\), \(s[0][5]\leftarrow 0\)
0	6	0	0	\(v[0][6]\leftarrow 0\), \(s[0][6]\leftarrow 0\)
0	7	0	0	\(v[0][7]\leftarrow 0\), \(s[0][7]\leftarrow 0\)
0	8	0	0	\(v[0][8]\leftarrow 0\), \(s[0][8]\leftarrow 0\)
1	0	0	0	\(\max\{v[0][0]\}=0\)
1	1	0	0	\(\max\{v[0][1]\}=0\)
1	2	5	1	\(\max\{v[0][2],\,p[1]{+}v[0][0]\}=\max\{0,5\}=5\)
1	3	5	1	\(\max\{v[0][3],\,p[1]{+}v[0][1]\}=\max\{0,5\}=5\)
1	4	10	2	\(\max\{v[0][4],\,p[1]{+}v[0][2],\,2p[1]{+}v[0][0]\}=\max\{0,5,10\}=10\)
1	5	10	2	\(\max\{v[0][5],\,p[1]{+}v[0][3],\,2p[1]{+}v[0][1]\}=\max\{0,5,10\}=10\)
1	6	15	3	\(\max\{v[0][6],\,p[1]{+}v[0][4],\,2p[1]{+}v[0][2],\,3p[1]{+}v[0][0]\}=\max\{0,5,10,15\}=15\)
1	7	15	3	\(\max\{v[0][7],\,p[1]{+}v[0][5],\,2p[1]{+}v[0][3],\,3p[1]{+}v[0][1]\}=\max\{0,5,10,15\}=15\)
1	8	15	3	\(\max\{v[0][8],\,p[1]{+}v[0][6],\,2p[1]{+}v[0][4],\,3p[1]{+}v[0][2]\}=\max\{0,5,10,15\}=15\)
2	0	0	0	\(\max\{v[1][0]\}=0\)
2	1	0	0	\(\max\{v[1][1]\}=0\)
2	2	5	0	\(\max\{v[1][2]\}=5\)
2	3	5	0	\(\max\{v[1][3]\}=5\)
2	4	10	0	\(\max\{v[1][4]\}=10\)
2	5	10	0	\(\max\{v[1][5],\,p[2]{+}v[1][0]\}=\max\{10,9\}=10\)
2	6	15	0	\(\max\{v[1][6],\,p[2]{+}v[1][1]\}=\max\{15,9\}=15\)
2	7	15	0	\(\max\{v[1][7],\,p[2]{+}v[1][2]\}=\max\{15,14\}=15\)
2	8	15	0	\(\max\{v[1][8],\,p[2]{+}v[1][3]\}=\max\{15,14\}=15\)

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

\[ \begin{array}{l|rrrrrrrrr} \hline {v[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 5 & 5 & 10 & 10 & 15 & 15 & 15 \\ {j=2} & 0 & 0 & 5 & 5 & 10 & 10 & 15 & 15 & 15 \\ \hline \end{array} \]

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

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

Abbiamo la seguente matrice \(s\):

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

Possiamo ricostruire una soluzione ottima partendo da \(j=2\) e \(k=8\) come segue:

Iterazione	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	Azione
-	-	-	-	0	\(k=8\)
1	2	8	0	0	\(x[2]\leftarrow 0\), \(k\leftarrow 8-0\cdot5=8\)
2	1	8	3	3	\(x[1]\leftarrow 3\), \(k\leftarrow 8-3\cdot2=2\)

Quindi il vettore

\[ (3,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[2][8]=15. \]

Esercizio 19.5: Esercizio 5: problema dello zaino limitato

Consideriamo la seguente istanza del BKP, in cui lo zaino ha capacità \(c=9\) e i profitti, i pesi e i limiti associati ai tipi di oggetto sono:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni iterazione, i valori delle matrici \(v\) e \(s\).
Usando la matrice \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,x_3)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo dell'algoritmo di PD bottom-up

Per ogni passo dell'algoritmo di PD, la tabella riporta i valori di \(j\) e \(k\), le celle \(v[j][k]\) e \(s[j][k]\) e l'operazione eseguita.

\(j\)	\(k\)	\(v[j][k]\)	\(s[j][k]\)	Azione
0	0	0	0	\(v[0][0]\leftarrow 0\), \(s[0][0]\leftarrow 0\)
0	1	0	0	\(v[0][1]\leftarrow 0\), \(s[0][1]\leftarrow 0\)
0	2	0	0	\(v[0][2]\leftarrow 0\), \(s[0][2]\leftarrow 0\)
0	3	0	0	\(v[0][3]\leftarrow 0\), \(s[0][3]\leftarrow 0\)
0	4	0	0	\(v[0][4]\leftarrow 0\), \(s[0][4]\leftarrow 0\)
0	5	0	0	\(v[0][5]\leftarrow 0\), \(s[0][5]\leftarrow 0\)
0	6	0	0	\(v[0][6]\leftarrow 0\), \(s[0][6]\leftarrow 0\)
0	7	0	0	\(v[0][7]\leftarrow 0\), \(s[0][7]\leftarrow 0\)
0	8	0	0	\(v[0][8]\leftarrow 0\), \(s[0][8]\leftarrow 0\)
0	9	0	0	\(v[0][9]\leftarrow 0\), \(s[0][9]\leftarrow 0\)
1	0	0	0	\(\max\{v[0][0]\}=0\)
1	1	0	0	\(\max\{v[0][1]\}=0\)
1	2	0	0	\(\max\{v[0][2]\}=0\)
1	3	4	1	\(\max\{v[0][3],\,p[1]{+}v[0][0]\}=\max\{0,4\}=4\)
1	4	4	1	\(\max\{v[0][4],\,p[1]{+}v[0][1]\}=\max\{0,4\}=4\)
1	5	4	1	\(\max\{v[0][5],\,p[1]{+}v[0][2]\}=\max\{0,4\}=4\)
1	6	8	2	\(\max\{v[0][6],\,p[1]{+}v[0][3],\,2p[1]{+}v[0][0]\}=\max\{0,4,8\}=8\)
1	7	8	2	\(\max\{v[0][7],\,p[1]{+}v[0][4],\,2p[1]{+}v[0][1]\}=\max\{0,4,8\}=8\)
1	8	8	2	\(\max\{v[0][8],\,p[1]{+}v[0][5],\,2p[1]{+}v[0][2]\}=\max\{0,4,8\}=8\)
1	9	8	2	\(\max\{v[0][9],\,p[1]{+}v[0][6],\,2p[1]{+}v[0][3]\}=\max\{0,4,8\}=8\)
2	0	0	0	\(\max\{v[1][0]\}=0\)
2	1	0	0	\(\max\{v[1][1]\}=0\)
2	2	0	0	\(\max\{v[1][2]\}=0\)
2	3	4	0	\(\max\{v[1][3]\}=4\)
2	4	5	1	\(\max\{v[1][4],\,p[2]{+}v[1][0]\}=\max\{4,5\}=5\)
2	5	5	1	\(\max\{v[1][5],\,p[2]{+}v[1][1]\}=\max\{4,5\}=5\)
2	6	8	0	\(\max\{v[1][6],\,p[2]{+}v[1][2]\}=\max\{8,5\}=8\)
2	7	9	1	\(\max\{v[1][7],\,p[2]{+}v[1][3]\}=\max\{8,9\}=9\)
2	8	9	1	\(\max\{v[1][8],\,p[2]{+}v[1][4]\}=\max\{8,9\}=9\)
2	9	9	1	\(\max\{v[1][9],\,p[2]{+}v[1][5]\}=\max\{8,9\}=9\)
3	0	0	0	\(\max\{v[2][0]\}=0\)
3	1	0	0	\(\max\{v[2][1]\}=0\)
3	2	3	1	\(\max\{v[2][2],\,p[3]{+}v[2][0]\}=\max\{0,3\}=3\)
3	3	4	0	\(\max\{v[2][3],\,p[3]{+}v[2][1]\}=\max\{4,3\}=4\)
3	4	6	2	\(\max\{v[2][4],\,p[3]{+}v[2][2],\,2p[3]{+}v[2][0]\}=\max\{5,3,6\}=6\)
3	5	7	1	\(\max\{v[2][5],\,p[3]{+}v[2][3],\,2p[3]{+}v[2][1]\}=\max\{5,7,6\}=7\)
3	6	8	0	\(\max\{v[2][6],\,p[3]{+}v[2][4],\,2p[3]{+}v[2][2]\}=\max\{8,8,6\}=8\)
3	7	10	2	\(\max\{v[2][7],\,p[3]{+}v[2][5],\,2p[3]{+}v[2][3]\}=\max\{9,8,10\}=10\)
3	8	11	1	\(\max\{v[2][8],\,p[3]{+}v[2][6],\,2p[3]{+}v[2][4]\}=\max\{9,11,11\}=11\)
3	9	12	1	\(\max\{v[2][9],\,p[3]{+}v[2][7],\,2p[3]{+}v[2][5]\}=\max\{9,12,11\}=12\)

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

\[ \begin{array}{l|rrrrrrrrrr} \hline {v[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 0 & 4 & 4 & 4 & 8 & 8 & 8 & 8 \\ {j=2} & 0 & 0 & 0 & 4 & 5 & 5 & 8 & 9 & 9 & 9 \\ {j=3} & 0 & 0 & 3 & 4 & 6 & 7 & 8 & 10 & 11 & 12 \\ \hline \end{array} \]

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

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

Abbiamo la seguente matrice \(s\):

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

Possiamo ricostruire una soluzione ottima partendo da \(j=3\) e \(k=9\) come segue:

Iterazione	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	Azione
-	-	-	-	0	0	0	\(k=9\)
1	3	9	1	0	0	1	\(x[3]\leftarrow 1\), \(k\leftarrow 9-1\cdot2=7\)
2	2	7	1	0	1	1	\(x[2]\leftarrow 1\), \(k\leftarrow 7-1\cdot4=3\)
3	1	3	1	1	1	1	\(x[1]\leftarrow 1\), \(k\leftarrow 3-1\cdot3=0\)

Quindi il vettore

\[ (1,1,1) \]

è una soluzione ottima. Il valore ottimo è

\[ v[3][9]=12. \]