Esercizi · PD per il problema dello zaino illimitato¶

Esercizi · Capitolo 18 · ogni soluzione si apre con un clic · Capitolo 18: Zaino illimitato (UKP) · Eserciziario, volume 3 (PDF)

Esercizio 18.1: I due algoritmi di PD per l'UKP (4 tipi di oggetto, \(c=7\))

Consideriamo la seguente istanza dell'UKP, in cui lo zaino ha capacità \(c=7\), ogni tipo di oggetto è disponibile in infinite copie e i profitti e i pesi dei tipi di oggetto sono:

\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 4 & 5 & 10 & 11 \\ {w_j} & 2 & 3 & 5 & 6 \\ \hline \end{array} \]

Domande

Mostrare l'esecuzione del primo algoritmo di PD bottom-up riportando, per ogni iterazione, i valori del vettore \(v\) e i valori del vettore \(s\).
Usando il vettore \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,\dots,x_n)\) e riportare il valore ottimo.
Mostrare l'esecuzione del secondo 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,\dots,x_n)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo del primo algoritmo di PD bottom-up

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

\(k\)	\(j\)	\(v[k]\)	\(s[k]\)	\(m\)	\(t\)	Azione
\(-\)	\(-\)	0	\(-\)	\(-\)	\(-\)	\(v[0]\leftarrow 0\)
1	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
1	1	\(-\)	\(-\)	0	0	\(w[1]=2>k=1\): nessun aggiornamento
1	2	\(-\)	\(-\)	0	0	\(w[2]=3>k=1\): nessun aggiornamento
1	3	\(-\)	\(-\)	0	0	\(w[3]=5>k=1\): nessun aggiornamento
1	4	\(-\)	\(-\)	0	0	\(w[4]=6>k=1\): nessun aggiornamento
1	\(-\)	0	0	0	0	\(v[1]\leftarrow 0\), \(s[1]\leftarrow 0\)
2	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
2	1	\(-\)	\(-\)	4	1	\(p[1]+v[0]=4+0=4>m=0\): \(m\leftarrow 4\), \(t\leftarrow 1\)
2	2	\(-\)	\(-\)	4	1	\(w[2]=3>k=2\): nessun aggiornamento
2	3	\(-\)	\(-\)	4	1	\(w[3]=5>k=2\): nessun aggiornamento
2	4	\(-\)	\(-\)	4	1	\(w[4]=6>k=2\): nessun aggiornamento
2	\(-\)	4	1	4	1	\(v[2]\leftarrow 4\), \(s[2]\leftarrow 1\)
3	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
3	1	\(-\)	\(-\)	4	1	\(p[1]+v[1]=4+0=4>m=0\): \(m\leftarrow 4\), \(t\leftarrow 1\)
3	2	\(-\)	\(-\)	5	2	\(p[2]+v[0]=5+0=5>m=4\): \(m\leftarrow 5\), \(t\leftarrow 2\)
3	3	\(-\)	\(-\)	5	2	\(w[3]=5>k=3\): nessun aggiornamento
3	4	\(-\)	\(-\)	5	2	\(w[4]=6>k=3\): nessun aggiornamento
3	\(-\)	5	2	5	2	\(v[3]\leftarrow 5\), \(s[3]\leftarrow 2\)
4	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
4	1	\(-\)	\(-\)	8	1	\(p[1]+v[2]=4+4=8>m=0\): \(m\leftarrow 8\), \(t\leftarrow 1\)
4	2	\(-\)	\(-\)	8	1	\(p[2]+v[1]=5+0=5\le m=8\): nessun aggiornamento
4	3	\(-\)	\(-\)	8	1	\(w[3]=5>k=4\): nessun aggiornamento
4	4	\(-\)	\(-\)	8	1	\(w[4]=6>k=4\): nessun aggiornamento
4	\(-\)	8	1	8	1	\(v[4]\leftarrow 8\), \(s[4]\leftarrow 1\)
5	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
5	1	\(-\)	\(-\)	9	1	\(p[1]+v[3]=4+5=9>m=0\): \(m\leftarrow 9\), \(t\leftarrow 1\)
5	2	\(-\)	\(-\)	9	1	\(p[2]+v[2]=5+4=9\le m=9\): nessun aggiornamento
5	3	\(-\)	\(-\)	10	3	\(p[3]+v[0]=10+0=10>m=9\): \(m\leftarrow 10\), \(t\leftarrow 3\)
5	4	\(-\)	\(-\)	10	3	\(w[4]=6>k=5\): nessun aggiornamento
5	\(-\)	10	3	10	3	\(v[5]\leftarrow 10\), \(s[5]\leftarrow 3\)
6	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
6	1	\(-\)	\(-\)	12	1	\(p[1]+v[4]=4+8=12>m=0\): \(m\leftarrow 12\), \(t\leftarrow 1\)
6	2	\(-\)	\(-\)	12	1	\(p[2]+v[3]=5+5=10\le m=12\): nessun aggiornamento
6	3	\(-\)	\(-\)	12	1	\(p[3]+v[1]=10+0=10\le m=12\): nessun aggiornamento
6	4	\(-\)	\(-\)	12	1	\(p[4]+v[0]=11+0=11\le m=12\): nessun aggiornamento
6	\(-\)	12	1	12	1	\(v[6]\leftarrow 12\), \(s[6]\leftarrow 1\)
7	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
7	1	\(-\)	\(-\)	14	1	\(p[1]+v[5]=4+10=14>m=0\): \(m\leftarrow 14\), \(t\leftarrow 1\)
7	2	\(-\)	\(-\)	14	1	\(p[2]+v[4]=5+8=13\le m=14\): nessun aggiornamento
7	3	\(-\)	\(-\)	14	1	\(p[3]+v[2]=10+4=14\le m=14\): nessun aggiornamento
7	4	\(-\)	\(-\)	14	1	\(p[4]+v[1]=11+0=11\le m=14\): nessun aggiornamento
7	\(-\)	14	1	14	1	\(v[7]\leftarrow 14\), \(s[7]\leftarrow 1\)

Questo è il vettore \(v\) dopo l'esecuzione del primo algoritmo di PD:

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

Questo è il vettore \(s\) dopo l'esecuzione del primo algoritmo di PD:

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

Abbiamo il seguente vettore \(s\):

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

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

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

Quindi il vettore

\[ (1,0,1,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[7]=14. \]

Esecuzione passo per passo del secondo 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. Tutte le celle della riga \(j=0\) sono inizializzate a \(0\).

\(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	\(k<w[1]\): \(v[1][0]\leftarrow v[0][0]=0\), \(s[1][0]\leftarrow 0\)
1	1	0	0	\(k<w[1]\): \(v[1][1]\leftarrow v[0][1]=0\), \(s[1][1]\leftarrow 0\)
1	2	4	1	\(p[1]+v[1][0]=4+0>v[0][2]=0\): \(v[1][2]\leftarrow 4\), \(s[1][2]\leftarrow 1\)
1	3	4	1	\(p[1]+v[1][1]=4+0>v[0][3]=0\): \(v[1][3]\leftarrow 4\), \(s[1][3]\leftarrow 1\)
1	4	8	1	\(p[1]+v[1][2]=4+4>v[0][4]=0\): \(v[1][4]\leftarrow 8\), \(s[1][4]\leftarrow 1\)
1	5	8	1	\(p[1]+v[1][3]=4+4>v[0][5]=0\): \(v[1][5]\leftarrow 8\), \(s[1][5]\leftarrow 1\)
1	6	12	1	\(p[1]+v[1][4]=4+8>v[0][6]=0\): \(v[1][6]\leftarrow 12\), \(s[1][6]\leftarrow 1\)
1	7	12	1	\(p[1]+v[1][5]=4+8>v[0][7]=0\): \(v[1][7]\leftarrow 12\), \(s[1][7]\leftarrow 1\)
2	0	0	0	\(k<w[2]\): \(v[2][0]\leftarrow v[1][0]=0\), \(s[2][0]\leftarrow 0\)
2	1	0	0	\(k<w[2]\): \(v[2][1]\leftarrow v[1][1]=0\), \(s[2][1]\leftarrow 0\)
2	2	4	0	\(k<w[2]\): \(v[2][2]\leftarrow v[1][2]=4\), \(s[2][2]\leftarrow 0\)
2	3	5	1	\(p[2]+v[2][0]=5+0>v[1][3]=4\): \(v[2][3]\leftarrow 5\), \(s[2][3]\leftarrow 1\)
2	4	8	0	\(p[2]+v[2][1]=5+0\le v[1][4]=8\): \(v[2][4]\leftarrow 8\), \(s[2][4]\leftarrow 0\)
2	5	9	1	\(p[2]+v[2][2]=5+4>v[1][5]=8\): \(v[2][5]\leftarrow 9\), \(s[2][5]\leftarrow 1\)
2	6	12	0	\(p[2]+v[2][3]=5+5\le v[1][6]=12\): \(v[2][6]\leftarrow 12\), \(s[2][6]\leftarrow 0\)
2	7	13	1	\(p[2]+v[2][4]=5+8>v[1][7]=12\): \(v[2][7]\leftarrow 13\), \(s[2][7]\leftarrow 1\)
3	0	0	0	\(k<w[3]\): \(v[3][0]\leftarrow v[2][0]=0\), \(s[3][0]\leftarrow 0\)
3	1	0	0	\(k<w[3]\): \(v[3][1]\leftarrow v[2][1]=0\), \(s[3][1]\leftarrow 0\)
3	2	4	0	\(k<w[3]\): \(v[3][2]\leftarrow v[2][2]=4\), \(s[3][2]\leftarrow 0\)
3	3	5	0	\(k<w[3]\): \(v[3][3]\leftarrow v[2][3]=5\), \(s[3][3]\leftarrow 0\)
3	4	8	0	\(k<w[3]\): \(v[3][4]\leftarrow v[2][4]=8\), \(s[3][4]\leftarrow 0\)
3	5	10	1	\(p[3]+v[3][0]=10+0>v[2][5]=9\): \(v[3][5]\leftarrow 10\), \(s[3][5]\leftarrow 1\)
3	6	12	0	\(p[3]+v[3][1]=10+0\le v[2][6]=12\): \(v[3][6]\leftarrow 12\), \(s[3][6]\leftarrow 0\)
3	7	14	1	\(p[3]+v[3][2]=10+4>v[2][7]=13\): \(v[3][7]\leftarrow 14\), \(s[3][7]\leftarrow 1\)
4	0	0	0	\(k<w[4]\): \(v[4][0]\leftarrow v[3][0]=0\), \(s[4][0]\leftarrow 0\)
4	1	0	0	\(k<w[4]\): \(v[4][1]\leftarrow v[3][1]=0\), \(s[4][1]\leftarrow 0\)
4	2	4	0	\(k<w[4]\): \(v[4][2]\leftarrow v[3][2]=4\), \(s[4][2]\leftarrow 0\)
4	3	5	0	\(k<w[4]\): \(v[4][3]\leftarrow v[3][3]=5\), \(s[4][3]\leftarrow 0\)
4	4	8	0	\(k<w[4]\): \(v[4][4]\leftarrow v[3][4]=8\), \(s[4][4]\leftarrow 0\)
4	5	10	0	\(k<w[4]\): \(v[4][5]\leftarrow v[3][5]=10\), \(s[4][5]\leftarrow 0\)
4	6	12	0	\(p[4]+v[4][0]=11+0\le v[3][6]=12\): \(v[4][6]\leftarrow 12\), \(s[4][6]\leftarrow 0\)
4	7	14	0	\(p[4]+v[4][1]=11+0\le v[3][7]=14\): \(v[4][7]\leftarrow 14\), \(s[4][7]\leftarrow 0\)

Questa è la matrice \(v\) dopo l'esecuzione del secondo 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 & 0 & 4 & 4 & 8 & 8 & 12 & 12 \\ {j=2} & 0 & 0 & 4 & 5 & 8 & 9 & 12 & 13 \\ {j=3} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ {j=4} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ \hline \end{array} \]

Questa è la matrice \(s\) dopo l'esecuzione del secondo 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 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \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 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]

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

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

Quindi il vettore

\[ (1,0,1,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[4][7]=14. \]

Esercizio 18.2: I due algoritmi di PD per l'UKP (5 tipi di oggetto, \(c=8\))

Consideriamo la seguente istanza dell'UKP, in cui lo zaino ha capacità \(c=8\), ogni tipo di oggetto è disponibile in infinite copie e i profitti e i pesi dei tipi di oggetto sono:

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

Domande

Mostrare l'esecuzione del primo algoritmo di PD bottom-up riportando, per ogni iterazione, i valori del vettore \(v\) e i valori del vettore \(s\).
Usando il vettore \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,\dots,x_n)\) e riportare il valore ottimo.
Mostrare l'esecuzione del secondo 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,\dots,x_n)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo del primo algoritmo di PD bottom-up

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

\(k\)	\(j\)	\(v[k]\)	\(s[k]\)	\(m\)	\(t\)	Azione
\(-\)	\(-\)	0	\(-\)	\(-\)	\(-\)	\(v[0]\leftarrow 0\)
1	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
1	1	\(-\)	\(-\)	2	1	\(p[1]+v[0]=2+0=2>m=0\): \(m\leftarrow 2\), \(t\leftarrow 1\)
1	2	\(-\)	\(-\)	2	1	\(w[2]=2>k=1\): nessun aggiornamento
1	3	\(-\)	\(-\)	2	1	\(w[3]=3>k=1\): nessun aggiornamento
1	4	\(-\)	\(-\)	2	1	\(w[4]=4>k=1\): nessun aggiornamento
1	5	\(-\)	\(-\)	2	1	\(w[5]=5>k=1\): nessun aggiornamento
1	\(-\)	2	1	2	1	\(v[1]\leftarrow 2\), \(s[1]\leftarrow 1\)
2	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
2	1	\(-\)	\(-\)	4	1	\(p[1]+v[1]=2+2=4>m=0\): \(m\leftarrow 4\), \(t\leftarrow 1\)
2	2	\(-\)	\(-\)	5	2	\(p[2]+v[0]=5+0=5>m=4\): \(m\leftarrow 5\), \(t\leftarrow 2\)
2	3	\(-\)	\(-\)	5	2	\(w[3]=3>k=2\): nessun aggiornamento
2	4	\(-\)	\(-\)	5	2	\(w[4]=4>k=2\): nessun aggiornamento
2	5	\(-\)	\(-\)	5	2	\(w[5]=5>k=2\): nessun aggiornamento
2	\(-\)	5	2	5	2	\(v[2]\leftarrow 5\), \(s[2]\leftarrow 2\)
3	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
3	1	\(-\)	\(-\)	7	1	\(p[1]+v[2]=2+5=7>m=0\): \(m\leftarrow 7\), \(t\leftarrow 1\)
3	2	\(-\)	\(-\)	7	1	\(p[2]+v[1]=5+2=7\le m=7\): nessun aggiornamento
3	3	\(-\)	\(-\)	7	1	\(p[3]+v[0]=7+0=7\le m=7\): nessun aggiornamento
3	4	\(-\)	\(-\)	7	1	\(w[4]=4>k=3\): nessun aggiornamento
3	5	\(-\)	\(-\)	7	1	\(w[5]=5>k=3\): nessun aggiornamento
3	\(-\)	7	1	7	1	\(v[3]\leftarrow 7\), \(s[3]\leftarrow 1\)
4	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
4	1	\(-\)	\(-\)	9	1	\(p[1]+v[3]=2+7=9>m=0\): \(m\leftarrow 9\), \(t\leftarrow 1\)
4	2	\(-\)	\(-\)	10	2	\(p[2]+v[2]=5+5=10>m=9\): \(m\leftarrow 10\), \(t\leftarrow 2\)
4	3	\(-\)	\(-\)	10	2	\(p[3]+v[1]=7+2=9\le m=10\): nessun aggiornamento
4	4	\(-\)	\(-\)	10	2	\(p[4]+v[0]=8+0=8\le m=10\): nessun aggiornamento
4	5	\(-\)	\(-\)	10	2	\(w[5]=5>k=4\): nessun aggiornamento
4	\(-\)	10	2	10	2	\(v[4]\leftarrow 10\), \(s[4]\leftarrow 2\)
5	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
5	1	\(-\)	\(-\)	12	1	\(p[1]+v[4]=2+10=12>m=0\): \(m\leftarrow 12\), \(t\leftarrow 1\)
5	2	\(-\)	\(-\)	12	1	\(p[2]+v[3]=5+7=12\le m=12\): nessun aggiornamento
5	3	\(-\)	\(-\)	12	1	\(p[3]+v[2]=7+5=12\le m=12\): nessun aggiornamento
5	4	\(-\)	\(-\)	12	1	\(p[4]+v[1]=8+2=10\le m=12\): nessun aggiornamento
5	5	\(-\)	\(-\)	12	1	\(p[5]+v[0]=10+0=10\le m=12\): nessun aggiornamento
5	\(-\)	12	1	12	1	\(v[5]\leftarrow 12\), \(s[5]\leftarrow 1\)
6	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
6	1	\(-\)	\(-\)	14	1	\(p[1]+v[5]=2+12=14>m=0\): \(m\leftarrow 14\), \(t\leftarrow 1\)
6	2	\(-\)	\(-\)	15	2	\(p[2]+v[4]=5+10=15>m=14\): \(m\leftarrow 15\), \(t\leftarrow 2\)
6	3	\(-\)	\(-\)	15	2	\(p[3]+v[3]=7+7=14\le m=15\): nessun aggiornamento
6	4	\(-\)	\(-\)	15	2	\(p[4]+v[2]=8+5=13\le m=15\): nessun aggiornamento
6	5	\(-\)	\(-\)	15	2	\(p[5]+v[1]=10+2=12\le m=15\): nessun aggiornamento
6	\(-\)	15	2	15	2	\(v[6]\leftarrow 15\), \(s[6]\leftarrow 2\)
7	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
7	1	\(-\)	\(-\)	17	1	\(p[1]+v[6]=2+15=17>m=0\): \(m\leftarrow 17\), \(t\leftarrow 1\)
7	2	\(-\)	\(-\)	17	1	\(p[2]+v[5]=5+12=17\le m=17\): nessun aggiornamento
7	3	\(-\)	\(-\)	17	1	\(p[3]+v[4]=7+10=17\le m=17\): nessun aggiornamento
7	4	\(-\)	\(-\)	17	1	\(p[4]+v[3]=8+7=15\le m=17\): nessun aggiornamento
7	5	\(-\)	\(-\)	17	1	\(p[5]+v[2]=10+5=15\le m=17\): nessun aggiornamento
7	\(-\)	17	1	17	1	\(v[7]\leftarrow 17\), \(s[7]\leftarrow 1\)
8	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
8	1	\(-\)	\(-\)	19	1	\(p[1]+v[7]=2+17=19>m=0\): \(m\leftarrow 19\), \(t\leftarrow 1\)
8	2	\(-\)	\(-\)	20	2	\(p[2]+v[6]=5+15=20>m=19\): \(m\leftarrow 20\), \(t\leftarrow 2\)
8	3	\(-\)	\(-\)	20	2	\(p[3]+v[5]=7+12=19\le m=20\): nessun aggiornamento
8	4	\(-\)	\(-\)	20	2	\(p[4]+v[4]=8+10=18\le m=20\): nessun aggiornamento
8	5	\(-\)	\(-\)	20	2	\(p[5]+v[3]=10+7=17\le m=20\): nessun aggiornamento
8	\(-\)	20	2	20	2	\(v[8]\leftarrow 20\), \(s[8]\leftarrow 2\)

Questo è il vettore \(v\) dopo l'esecuzione del primo algoritmo di PD:

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

Questo è il vettore \(s\) dopo l'esecuzione del primo algoritmo di PD:

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

Abbiamo il seguente vettore \(s\):

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

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

Iterazione	\(k\)	\(s[k]\)	\(x[2]\)	Azione
-	-	-	0	\(k=8\)
1	8	2	1	\(x[2]\leftarrow 1\), \(k\leftarrow 8-2=6\)
2	6	2	2	\(x[2]\leftarrow 2\), \(k\leftarrow 6-2=4\)
3	4	2	3	\(x[2]\leftarrow 3\), \(k\leftarrow 4-2=2\)
4	2	2	4	\(x[2]\leftarrow 4\), \(k\leftarrow 2-2=0\)

Quindi il vettore

\[ (0,4,0,0,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[8]=20. \]

Esecuzione passo per passo del secondo 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. Tutte le celle della riga \(j=0\) sono inizializzate a \(0\).

\(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	\(k<w[1]\): \(v[1][0]\leftarrow v[0][0]=0\), \(s[1][0]\leftarrow 0\)
1	1	2	1	\(p[1]+v[1][0]=2+0>v[0][1]=0\): \(v[1][1]\leftarrow 2\), \(s[1][1]\leftarrow 1\)
1	2	4	1	\(p[1]+v[1][1]=2+2>v[0][2]=0\): \(v[1][2]\leftarrow 4\), \(s[1][2]\leftarrow 1\)
1	3	6	1	\(p[1]+v[1][2]=2+4>v[0][3]=0\): \(v[1][3]\leftarrow 6\), \(s[1][3]\leftarrow 1\)
1	4	8	1	\(p[1]+v[1][3]=2+6>v[0][4]=0\): \(v[1][4]\leftarrow 8\), \(s[1][4]\leftarrow 1\)
1	5	10	1	\(p[1]+v[1][4]=2+8>v[0][5]=0\): \(v[1][5]\leftarrow 10\), \(s[1][5]\leftarrow 1\)
1	6	12	1	\(p[1]+v[1][5]=2+10>v[0][6]=0\): \(v[1][6]\leftarrow 12\), \(s[1][6]\leftarrow 1\)
1	7	14	1	\(p[1]+v[1][6]=2+12>v[0][7]=0\): \(v[1][7]\leftarrow 14\), \(s[1][7]\leftarrow 1\)
1	8	16	1	\(p[1]+v[1][7]=2+14>v[0][8]=0\): \(v[1][8]\leftarrow 16\), \(s[1][8]\leftarrow 1\)
2	0	0	0	\(k<w[2]\): \(v[2][0]\leftarrow v[1][0]=0\), \(s[2][0]\leftarrow 0\)
2	1	2	0	\(k<w[2]\): \(v[2][1]\leftarrow v[1][1]=2\), \(s[2][1]\leftarrow 0\)
2	2	5	1	\(p[2]+v[2][0]=5+0>v[1][2]=4\): \(v[2][2]\leftarrow 5\), \(s[2][2]\leftarrow 1\)
2	3	7	1	\(p[2]+v[2][1]=5+2>v[1][3]=6\): \(v[2][3]\leftarrow 7\), \(s[2][3]\leftarrow 1\)
2	4	10	1	\(p[2]+v[2][2]=5+5>v[1][4]=8\): \(v[2][4]\leftarrow 10\), \(s[2][4]\leftarrow 1\)
2	5	12	1	\(p[2]+v[2][3]=5+7>v[1][5]=10\): \(v[2][5]\leftarrow 12\), \(s[2][5]\leftarrow 1\)
2	6	15	1	\(p[2]+v[2][4]=5+10>v[1][6]=12\): \(v[2][6]\leftarrow 15\), \(s[2][6]\leftarrow 1\)
2	7	17	1	\(p[2]+v[2][5]=5+12>v[1][7]=14\): \(v[2][7]\leftarrow 17\), \(s[2][7]\leftarrow 1\)
2	8	20	1	\(p[2]+v[2][6]=5+15>v[1][8]=16\): \(v[2][8]\leftarrow 20\), \(s[2][8]\leftarrow 1\)
3	0	0	0	\(k<w[3]\): \(v[3][0]\leftarrow v[2][0]=0\), \(s[3][0]\leftarrow 0\)
3	1	2	0	\(k<w[3]\): \(v[3][1]\leftarrow v[2][1]=2\), \(s[3][1]\leftarrow 0\)
3	2	5	0	\(k<w[3]\): \(v[3][2]\leftarrow v[2][2]=5\), \(s[3][2]\leftarrow 0\)
3	3	7	0	\(p[3]+v[3][0]=7+0\le v[2][3]=7\): \(v[3][3]\leftarrow 7\), \(s[3][3]\leftarrow 0\)
3	4	10	0	\(p[3]+v[3][1]=7+2\le v[2][4]=10\): \(v[3][4]\leftarrow 10\), \(s[3][4]\leftarrow 0\)
3	5	12	0	\(p[3]+v[3][2]=7+5\le v[2][5]=12\): \(v[3][5]\leftarrow 12\), \(s[3][5]\leftarrow 0\)
3	6	15	0	\(p[3]+v[3][3]=7+7\le v[2][6]=15\): \(v[3][6]\leftarrow 15\), \(s[3][6]\leftarrow 0\)
3	7	17	0	\(p[3]+v[3][4]=7+10\le v[2][7]=17\): \(v[3][7]\leftarrow 17\), \(s[3][7]\leftarrow 0\)
3	8	20	0	\(p[3]+v[3][5]=7+12\le v[2][8]=20\): \(v[3][8]\leftarrow 20\), \(s[3][8]\leftarrow 0\)
4	0	0	0	\(k<w[4]\): \(v[4][0]\leftarrow v[3][0]=0\), \(s[4][0]\leftarrow 0\)
4	1	2	0	\(k<w[4]\): \(v[4][1]\leftarrow v[3][1]=2\), \(s[4][1]\leftarrow 0\)
4	2	5	0	\(k<w[4]\): \(v[4][2]\leftarrow v[3][2]=5\), \(s[4][2]\leftarrow 0\)
4	3	7	0	\(k<w[4]\): \(v[4][3]\leftarrow v[3][3]=7\), \(s[4][3]\leftarrow 0\)
4	4	10	0	\(p[4]+v[4][0]=8+0\le v[3][4]=10\): \(v[4][4]\leftarrow 10\), \(s[4][4]\leftarrow 0\)
4	5	12	0	\(p[4]+v[4][1]=8+2\le v[3][5]=12\): \(v[4][5]\leftarrow 12\), \(s[4][5]\leftarrow 0\)
4	6	15	0	\(p[4]+v[4][2]=8+5\le v[3][6]=15\): \(v[4][6]\leftarrow 15\), \(s[4][6]\leftarrow 0\)
4	7	17	0	\(p[4]+v[4][3]=8+7\le v[3][7]=17\): \(v[4][7]\leftarrow 17\), \(s[4][7]\leftarrow 0\)
4	8	20	0	\(p[4]+v[4][4]=8+10\le v[3][8]=20\): \(v[4][8]\leftarrow 20\), \(s[4][8]\leftarrow 0\)
5	0	0	0	\(k<w[5]\): \(v[5][0]\leftarrow v[4][0]=0\), \(s[5][0]\leftarrow 0\)
5	1	2	0	\(k<w[5]\): \(v[5][1]\leftarrow v[4][1]=2\), \(s[5][1]\leftarrow 0\)
5	2	5	0	\(k<w[5]\): \(v[5][2]\leftarrow v[4][2]=5\), \(s[5][2]\leftarrow 0\)
5	3	7	0	\(k<w[5]\): \(v[5][3]\leftarrow v[4][3]=7\), \(s[5][3]\leftarrow 0\)
5	4	10	0	\(k<w[5]\): \(v[5][4]\leftarrow v[4][4]=10\), \(s[5][4]\leftarrow 0\)
5	5	12	0	\(p[5]+v[5][0]=10+0\le v[4][5]=12\): \(v[5][5]\leftarrow 12\), \(s[5][5]\leftarrow 0\)
5	6	15	0	\(p[5]+v[5][1]=10+2\le v[4][6]=15\): \(v[5][6]\leftarrow 15\), \(s[5][6]\leftarrow 0\)
5	7	17	0	\(p[5]+v[5][2]=10+5\le v[4][7]=17\): \(v[5][7]\leftarrow 17\), \(s[5][7]\leftarrow 0\)
5	8	20	0	\(p[5]+v[5][3]=10+7\le v[4][8]=20\): \(v[5][8]\leftarrow 20\), \(s[5][8]\leftarrow 0\)

Questa è la matrice \(v\) dopo l'esecuzione del secondo 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 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 \\ {j=2} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ {j=3} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ {j=4} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ {j=5} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ \hline \end{array} \]

Questa è la matrice \(s\) dopo l'esecuzione del secondo 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]

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

Iterazione	\(j\)	\(k\)	\(s[j][k]\)	\(x[2]\)	Azione
-	-	-	-	0	\(j=5\), \(k=8\)
1	5	8	0	0	\(j\leftarrow 4\)
2	4	8	0	0	\(j\leftarrow 3\)
3	3	8	0	0	\(j\leftarrow 2\)
4	2	8	1	1	\(x[2]\leftarrow 1\), \(k\leftarrow 8-2=6\)
5	2	6	1	2	\(x[2]\leftarrow 2\), \(k\leftarrow 6-2=4\)
6	2	4	1	3	\(x[2]\leftarrow 3\), \(k\leftarrow 4-2=2\)
7	2	2	1	4	\(x[2]\leftarrow 4\), \(k\leftarrow 2-2=0\)

Quindi il vettore

\[ (0,4,0,0,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[5][8]=20. \]

Esercizio 18.3: I due algoritmi di PD per l'UKP (4 tipi di oggetto, \(c=10\))

Consideriamo la seguente istanza dell'UKP, in cui lo zaino ha capacità \(c=10\), ogni tipo di oggetto è disponibile in infinite copie e i profitti e i pesi dei tipi di oggetto sono:

\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 6 & 10 & 12 & 13 \\ {w_j} & 3 & 4 & 6 & 7 \\ \hline \end{array} \]

Domande

Mostrare l'esecuzione del primo algoritmo di PD bottom-up riportando, per ogni iterazione, i valori del vettore \(v\) e i valori del vettore \(s\).
Usando il vettore \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,\dots,x_n)\) e riportare il valore ottimo.
Mostrare l'esecuzione del secondo 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,\dots,x_n)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo del primo algoritmo di PD bottom-up

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

\(k\)	\(j\)	\(v[k]\)	\(s[k]\)	\(m\)	\(t\)	Azione
\(-\)	\(-\)	0	\(-\)	\(-\)	\(-\)	\(v[0]\leftarrow 0\)
1	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
1	1	\(-\)	\(-\)	0	0	\(w[1]=3>k=1\): nessun aggiornamento
1	2	\(-\)	\(-\)	0	0	\(w[2]=4>k=1\): nessun aggiornamento
1	3	\(-\)	\(-\)	0	0	\(w[3]=6>k=1\): nessun aggiornamento
1	4	\(-\)	\(-\)	0	0	\(w[4]=7>k=1\): nessun aggiornamento
1	\(-\)	0	0	0	0	\(v[1]\leftarrow 0\), \(s[1]\leftarrow 0\)
2	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
2	1	\(-\)	\(-\)	0	0	\(w[1]=3>k=2\): nessun aggiornamento
2	2	\(-\)	\(-\)	0	0	\(w[2]=4>k=2\): nessun aggiornamento
2	3	\(-\)	\(-\)	0	0	\(w[3]=6>k=2\): nessun aggiornamento
2	4	\(-\)	\(-\)	0	0	\(w[4]=7>k=2\): nessun aggiornamento
2	\(-\)	0	0	0	0	\(v[2]\leftarrow 0\), \(s[2]\leftarrow 0\)
3	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
3	1	\(-\)	\(-\)	6	1	\(p[1]+v[0]=6+0=6>m=0\): \(m\leftarrow 6\), \(t\leftarrow 1\)
3	2	\(-\)	\(-\)	6	1	\(w[2]=4>k=3\): nessun aggiornamento
3	3	\(-\)	\(-\)	6	1	\(w[3]=6>k=3\): nessun aggiornamento
3	4	\(-\)	\(-\)	6	1	\(w[4]=7>k=3\): nessun aggiornamento
3	\(-\)	6	1	6	1	\(v[3]\leftarrow 6\), \(s[3]\leftarrow 1\)
4	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
4	1	\(-\)	\(-\)	6	1	\(p[1]+v[1]=6+0=6>m=0\): \(m\leftarrow 6\), \(t\leftarrow 1\)
4	2	\(-\)	\(-\)	10	2	\(p[2]+v[0]=10+0=10>m=6\): \(m\leftarrow 10\), \(t\leftarrow 2\)
4	3	\(-\)	\(-\)	10	2	\(w[3]=6>k=4\): nessun aggiornamento
4	4	\(-\)	\(-\)	10	2	\(w[4]=7>k=4\): nessun aggiornamento
4	\(-\)	10	2	10	2	\(v[4]\leftarrow 10\), \(s[4]\leftarrow 2\)
5	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
5	1	\(-\)	\(-\)	6	1	\(p[1]+v[2]=6+0=6>m=0\): \(m\leftarrow 6\), \(t\leftarrow 1\)
5	2	\(-\)	\(-\)	10	2	\(p[2]+v[1]=10+0=10>m=6\): \(m\leftarrow 10\), \(t\leftarrow 2\)
5	3	\(-\)	\(-\)	10	2	\(w[3]=6>k=5\): nessun aggiornamento
5	4	\(-\)	\(-\)	10	2	\(w[4]=7>k=5\): nessun aggiornamento
5	\(-\)	10	2	10	2	\(v[5]\leftarrow 10\), \(s[5]\leftarrow 2\)
6	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
6	1	\(-\)	\(-\)	12	1	\(p[1]+v[3]=6+6=12>m=0\): \(m\leftarrow 12\), \(t\leftarrow 1\)
6	2	\(-\)	\(-\)	12	1	\(p[2]+v[2]=10+0=10\le m=12\): nessun aggiornamento
6	3	\(-\)	\(-\)	12	1	\(p[3]+v[0]=12+0=12\le m=12\): nessun aggiornamento
6	4	\(-\)	\(-\)	12	1	\(w[4]=7>k=6\): nessun aggiornamento
6	\(-\)	12	1	12	1	\(v[6]\leftarrow 12\), \(s[6]\leftarrow 1\)
7	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
7	1	\(-\)	\(-\)	16	1	\(p[1]+v[4]=6+10=16>m=0\): \(m\leftarrow 16\), \(t\leftarrow 1\)
7	2	\(-\)	\(-\)	16	1	\(p[2]+v[3]=10+6=16\le m=16\): nessun aggiornamento
7	3	\(-\)	\(-\)	16	1	\(p[3]+v[1]=12+0=12\le m=16\): nessun aggiornamento
7	4	\(-\)	\(-\)	16	1	\(p[4]+v[0]=13+0=13\le m=16\): nessun aggiornamento
7	\(-\)	16	1	16	1	\(v[7]\leftarrow 16\), \(s[7]\leftarrow 1\)
8	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
8	1	\(-\)	\(-\)	16	1	\(p[1]+v[5]=6+10=16>m=0\): \(m\leftarrow 16\), \(t\leftarrow 1\)
8	2	\(-\)	\(-\)	20	2	\(p[2]+v[4]=10+10=20>m=16\): \(m\leftarrow 20\), \(t\leftarrow 2\)
8	3	\(-\)	\(-\)	20	2	\(p[3]+v[2]=12+0=12\le m=20\): nessun aggiornamento
8	4	\(-\)	\(-\)	20	2	\(p[4]+v[1]=13+0=13\le m=20\): nessun aggiornamento
8	\(-\)	20	2	20	2	\(v[8]\leftarrow 20\), \(s[8]\leftarrow 2\)
9	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
9	1	\(-\)	\(-\)	18	1	\(p[1]+v[6]=6+12=18>m=0\): \(m\leftarrow 18\), \(t\leftarrow 1\)
9	2	\(-\)	\(-\)	20	2	\(p[2]+v[5]=10+10=20>m=18\): \(m\leftarrow 20\), \(t\leftarrow 2\)
9	3	\(-\)	\(-\)	20	2	\(p[3]+v[3]=12+6=18\le m=20\): nessun aggiornamento
9	4	\(-\)	\(-\)	20	2	\(p[4]+v[2]=13+0=13\le m=20\): nessun aggiornamento
9	\(-\)	20	2	20	2	\(v[9]\leftarrow 20\), \(s[9]\leftarrow 2\)
10	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
10	1	\(-\)	\(-\)	22	1	\(p[1]+v[7]=6+16=22>m=0\): \(m\leftarrow 22\), \(t\leftarrow 1\)
10	2	\(-\)	\(-\)	22	1	\(p[2]+v[6]=10+12=22\le m=22\): nessun aggiornamento
10	3	\(-\)	\(-\)	22	1	\(p[3]+v[4]=12+10=22\le m=22\): nessun aggiornamento
10	4	\(-\)	\(-\)	22	1	\(p[4]+v[3]=13+6=19\le m=22\): nessun aggiornamento
10	\(-\)	22	1	22	1	\(v[10]\leftarrow 22\), \(s[10]\leftarrow 1\)

Questo è il vettore \(v\) dopo l'esecuzione del primo algoritmo di PD:

\[ \begin{array}{l|rrrrrrrrrrr} \hline & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {v[k]} & 0 & 0 & 0 & 6 & 10 & 10 & 12 & 16 & 20 & 20 & 22 \\ \hline \end{array} \]

Questo è il vettore \(s\) dopo l'esecuzione del primo algoritmo di PD:

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

Abbiamo il seguente vettore \(s\):

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

Possiamo ricostruire una soluzione ottima partendo da \(k=10\) come segue:

Iterazione	\(k\)	\(s[k]\)	\(x[1]\)	\(x[2]\)	Azione
-	-	-	0	0	\(k=10\)
1	10	1	1	0	\(x[1]\leftarrow 1\), \(k\leftarrow 10-3=7\)
2	7	1	2	0	\(x[1]\leftarrow 2\), \(k\leftarrow 7-3=4\)
3	4	2	2	1	\(x[2]\leftarrow 1\), \(k\leftarrow 4-4=0\)

Quindi il vettore

\[ (2,1,0,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[10]=22. \]

Esecuzione passo per passo del secondo 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. Tutte le celle della riga \(j=0\) sono inizializzate a \(0\).

\(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\)
0	10	0	0	\(v[0][10]\leftarrow 0\), \(s[0][10]\leftarrow 0\)
1	0	0	0	\(k<w[1]\): \(v[1][0]\leftarrow v[0][0]=0\), \(s[1][0]\leftarrow 0\)
1	1	0	0	\(k<w[1]\): \(v[1][1]\leftarrow v[0][1]=0\), \(s[1][1]\leftarrow 0\)
1	2	0	0	\(k<w[1]\): \(v[1][2]\leftarrow v[0][2]=0\), \(s[1][2]\leftarrow 0\)
1	3	6	1	\(p[1]+v[1][0]=6+0>v[0][3]=0\): \(v[1][3]\leftarrow 6\), \(s[1][3]\leftarrow 1\)
1	4	6	1	\(p[1]+v[1][1]=6+0>v[0][4]=0\): \(v[1][4]\leftarrow 6\), \(s[1][4]\leftarrow 1\)
1	5	6	1	\(p[1]+v[1][2]=6+0>v[0][5]=0\): \(v[1][5]\leftarrow 6\), \(s[1][5]\leftarrow 1\)
1	6	12	1	\(p[1]+v[1][3]=6+6>v[0][6]=0\): \(v[1][6]\leftarrow 12\), \(s[1][6]\leftarrow 1\)
1	7	12	1	\(p[1]+v[1][4]=6+6>v[0][7]=0\): \(v[1][7]\leftarrow 12\), \(s[1][7]\leftarrow 1\)
1	8	12	1	\(p[1]+v[1][5]=6+6>v[0][8]=0\): \(v[1][8]\leftarrow 12\), \(s[1][8]\leftarrow 1\)
1	9	18	1	\(p[1]+v[1][6]=6+12>v[0][9]=0\): \(v[1][9]\leftarrow 18\), \(s[1][9]\leftarrow 1\)
1	10	18	1	\(p[1]+v[1][7]=6+12>v[0][10]=0\): \(v[1][10]\leftarrow 18\), \(s[1][10]\leftarrow 1\)
2	0	0	0	\(k<w[2]\): \(v[2][0]\leftarrow v[1][0]=0\), \(s[2][0]\leftarrow 0\)
2	1	0	0	\(k<w[2]\): \(v[2][1]\leftarrow v[1][1]=0\), \(s[2][1]\leftarrow 0\)
2	2	0	0	\(k<w[2]\): \(v[2][2]\leftarrow v[1][2]=0\), \(s[2][2]\leftarrow 0\)
2	3	6	0	\(k<w[2]\): \(v[2][3]\leftarrow v[1][3]=6\), \(s[2][3]\leftarrow 0\)
2	4	10	1	\(p[2]+v[2][0]=10+0>v[1][4]=6\): \(v[2][4]\leftarrow 10\), \(s[2][4]\leftarrow 1\)
2	5	10	1	\(p[2]+v[2][1]=10+0>v[1][5]=6\): \(v[2][5]\leftarrow 10\), \(s[2][5]\leftarrow 1\)
2	6	12	0	\(p[2]+v[2][2]=10+0\le v[1][6]=12\): \(v[2][6]\leftarrow 12\), \(s[2][6]\leftarrow 0\)
2	7	16	1	\(p[2]+v[2][3]=10+6>v[1][7]=12\): \(v[2][7]\leftarrow 16\), \(s[2][7]\leftarrow 1\)
2	8	20	1	\(p[2]+v[2][4]=10+10>v[1][8]=12\): \(v[2][8]\leftarrow 20\), \(s[2][8]\leftarrow 1\)
2	9	20	1	\(p[2]+v[2][5]=10+10>v[1][9]=18\): \(v[2][9]\leftarrow 20\), \(s[2][9]\leftarrow 1\)
2	10	22	1	\(p[2]+v[2][6]=10+12>v[1][10]=18\): \(v[2][10]\leftarrow 22\), \(s[2][10]\leftarrow 1\)
3	0	0	0	\(k<w[3]\): \(v[3][0]\leftarrow v[2][0]=0\), \(s[3][0]\leftarrow 0\)
3	1	0	0	\(k<w[3]\): \(v[3][1]\leftarrow v[2][1]=0\), \(s[3][1]\leftarrow 0\)
3	2	0	0	\(k<w[3]\): \(v[3][2]\leftarrow v[2][2]=0\), \(s[3][2]\leftarrow 0\)
3	3	6	0	\(k<w[3]\): \(v[3][3]\leftarrow v[2][3]=6\), \(s[3][3]\leftarrow 0\)
3	4	10	0	\(k<w[3]\): \(v[3][4]\leftarrow v[2][4]=10\), \(s[3][4]\leftarrow 0\)
3	5	10	0	\(k<w[3]\): \(v[3][5]\leftarrow v[2][5]=10\), \(s[3][5]\leftarrow 0\)
3	6	12	0	\(p[3]+v[3][0]=12+0\le v[2][6]=12\): \(v[3][6]\leftarrow 12\), \(s[3][6]\leftarrow 0\)
3	7	16	0	\(p[3]+v[3][1]=12+0\le v[2][7]=16\): \(v[3][7]\leftarrow 16\), \(s[3][7]\leftarrow 0\)
3	8	20	0	\(p[3]+v[3][2]=12+0\le v[2][8]=20\): \(v[3][8]\leftarrow 20\), \(s[3][8]\leftarrow 0\)
3	9	20	0	\(p[3]+v[3][3]=12+6\le v[2][9]=20\): \(v[3][9]\leftarrow 20\), \(s[3][9]\leftarrow 0\)
3	10	22	0	\(p[3]+v[3][4]=12+10\le v[2][10]=22\): \(v[3][10]\leftarrow 22\), \(s[3][10]\leftarrow 0\)
4	0	0	0	\(k<w[4]\): \(v[4][0]\leftarrow v[3][0]=0\), \(s[4][0]\leftarrow 0\)
4	1	0	0	\(k<w[4]\): \(v[4][1]\leftarrow v[3][1]=0\), \(s[4][1]\leftarrow 0\)
4	2	0	0	\(k<w[4]\): \(v[4][2]\leftarrow v[3][2]=0\), \(s[4][2]\leftarrow 0\)
4	3	6	0	\(k<w[4]\): \(v[4][3]\leftarrow v[3][3]=6\), \(s[4][3]\leftarrow 0\)
4	4	10	0	\(k<w[4]\): \(v[4][4]\leftarrow v[3][4]=10\), \(s[4][4]\leftarrow 0\)
4	5	10	0	\(k<w[4]\): \(v[4][5]\leftarrow v[3][5]=10\), \(s[4][5]\leftarrow 0\)
4	6	12	0	\(k<w[4]\): \(v[4][6]\leftarrow v[3][6]=12\), \(s[4][6]\leftarrow 0\)
4	7	16	0	\(p[4]+v[4][0]=13+0\le v[3][7]=16\): \(v[4][7]\leftarrow 16\), \(s[4][7]\leftarrow 0\)
4	8	20	0	\(p[4]+v[4][1]=13+0\le v[3][8]=20\): \(v[4][8]\leftarrow 20\), \(s[4][8]\leftarrow 0\)
4	9	20	0	\(p[4]+v[4][2]=13+0\le v[3][9]=20\): \(v[4][9]\leftarrow 20\), \(s[4][9]\leftarrow 0\)
4	10	22	0	\(p[4]+v[4][3]=13+6\le v[3][10]=22\): \(v[4][10]\leftarrow 22\), \(s[4][10]\leftarrow 0\)

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

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

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

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

Abbiamo la seguente matrice \(s\):

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

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

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

Quindi il vettore

\[ (2,1,0,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[4][10]=22. \]

La soluzione ottima non è unica: anche \((0,1,1,0)\), con peso totale \(4+6=10\) e profitto totale \(10+12=22\), è ottima. Entrambi gli algoritmi di PD trovano \((2,1,0,0)\), perché aggiornano il valore memorizzato solo quando migliora strettamente.

Esercizio 18.4: I due algoritmi di PD per l'UKP (4 tipi di oggetto, \(c=9\))

Consideriamo la seguente istanza dell'UKP, in cui lo zaino ha capacità \(c=9\), ogni tipo di oggetto è disponibile in infinite copie e i profitti e i pesi dei tipi di oggetto sono:

\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 5 & 6 & 14 & 18 \\ {w_j} & 2 & 3 & 6 & 7 \\ \hline \end{array} \]

Domande

Mostrare l'esecuzione del primo algoritmo di PD bottom-up riportando, per ogni iterazione, i valori del vettore \(v\) e i valori del vettore \(s\).
Usando il vettore \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,\dots,x_n)\) e riportare il valore ottimo.
Mostrare l'esecuzione del secondo 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,\dots,x_n)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo del primo algoritmo di PD bottom-up

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

\(k\)	\(j\)	\(v[k]\)	\(s[k]\)	\(m\)	\(t\)	Azione
\(-\)	\(-\)	0	\(-\)	\(-\)	\(-\)	\(v[0]\leftarrow 0\)
1	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
1	1	\(-\)	\(-\)	0	0	\(w[1]=2>k=1\): nessun aggiornamento
1	2	\(-\)	\(-\)	0	0	\(w[2]=3>k=1\): nessun aggiornamento
1	3	\(-\)	\(-\)	0	0	\(w[3]=6>k=1\): nessun aggiornamento
1	4	\(-\)	\(-\)	0	0	\(w[4]=7>k=1\): nessun aggiornamento
1	\(-\)	0	0	0	0	\(v[1]\leftarrow 0\), \(s[1]\leftarrow 0\)
2	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
2	1	\(-\)	\(-\)	5	1	\(p[1]+v[0]=5+0=5>m=0\): \(m\leftarrow 5\), \(t\leftarrow 1\)
2	2	\(-\)	\(-\)	5	1	\(w[2]=3>k=2\): nessun aggiornamento
2	3	\(-\)	\(-\)	5	1	\(w[3]=6>k=2\): nessun aggiornamento
2	4	\(-\)	\(-\)	5	1	\(w[4]=7>k=2\): nessun aggiornamento
2	\(-\)	5	1	5	1	\(v[2]\leftarrow 5\), \(s[2]\leftarrow 1\)
3	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
3	1	\(-\)	\(-\)	5	1	\(p[1]+v[1]=5+0=5>m=0\): \(m\leftarrow 5\), \(t\leftarrow 1\)
3	2	\(-\)	\(-\)	6	2	\(p[2]+v[0]=6+0=6>m=5\): \(m\leftarrow 6\), \(t\leftarrow 2\)
3	3	\(-\)	\(-\)	6	2	\(w[3]=6>k=3\): nessun aggiornamento
3	4	\(-\)	\(-\)	6	2	\(w[4]=7>k=3\): nessun aggiornamento
3	\(-\)	6	2	6	2	\(v[3]\leftarrow 6\), \(s[3]\leftarrow 2\)
4	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
4	1	\(-\)	\(-\)	10	1	\(p[1]+v[2]=5+5=10>m=0\): \(m\leftarrow 10\), \(t\leftarrow 1\)
4	2	\(-\)	\(-\)	10	1	\(p[2]+v[1]=6+0=6\le m=10\): nessun aggiornamento
4	3	\(-\)	\(-\)	10	1	\(w[3]=6>k=4\): nessun aggiornamento
4	4	\(-\)	\(-\)	10	1	\(w[4]=7>k=4\): nessun aggiornamento
4	\(-\)	10	1	10	1	\(v[4]\leftarrow 10\), \(s[4]\leftarrow 1\)
5	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
5	1	\(-\)	\(-\)	11	1	\(p[1]+v[3]=5+6=11>m=0\): \(m\leftarrow 11\), \(t\leftarrow 1\)
5	2	\(-\)	\(-\)	11	1	\(p[2]+v[2]=6+5=11\le m=11\): nessun aggiornamento
5	3	\(-\)	\(-\)	11	1	\(w[3]=6>k=5\): nessun aggiornamento
5	4	\(-\)	\(-\)	11	1	\(w[4]=7>k=5\): nessun aggiornamento
5	\(-\)	11	1	11	1	\(v[5]\leftarrow 11\), \(s[5]\leftarrow 1\)
6	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
6	1	\(-\)	\(-\)	15	1	\(p[1]+v[4]=5+10=15>m=0\): \(m\leftarrow 15\), \(t\leftarrow 1\)
6	2	\(-\)	\(-\)	15	1	\(p[2]+v[3]=6+6=12\le m=15\): nessun aggiornamento
6	3	\(-\)	\(-\)	15	1	\(p[3]+v[0]=14+0=14\le m=15\): nessun aggiornamento
6	4	\(-\)	\(-\)	15	1	\(w[4]=7>k=6\): nessun aggiornamento
6	\(-\)	15	1	15	1	\(v[6]\leftarrow 15\), \(s[6]\leftarrow 1\)
7	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
7	1	\(-\)	\(-\)	16	1	\(p[1]+v[5]=5+11=16>m=0\): \(m\leftarrow 16\), \(t\leftarrow 1\)
7	2	\(-\)	\(-\)	16	1	\(p[2]+v[4]=6+10=16\le m=16\): nessun aggiornamento
7	3	\(-\)	\(-\)	16	1	\(p[3]+v[1]=14+0=14\le m=16\): nessun aggiornamento
7	4	\(-\)	\(-\)	18	4	\(p[4]+v[0]=18+0=18>m=16\): \(m\leftarrow 18\), \(t\leftarrow 4\)
7	\(-\)	18	4	18	4	\(v[7]\leftarrow 18\), \(s[7]\leftarrow 4\)
8	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
8	1	\(-\)	\(-\)	20	1	\(p[1]+v[6]=5+15=20>m=0\): \(m\leftarrow 20\), \(t\leftarrow 1\)
8	2	\(-\)	\(-\)	20	1	\(p[2]+v[5]=6+11=17\le m=20\): nessun aggiornamento
8	3	\(-\)	\(-\)	20	1	\(p[3]+v[2]=14+5=19\le m=20\): nessun aggiornamento
8	4	\(-\)	\(-\)	20	1	\(p[4]+v[1]=18+0=18\le m=20\): nessun aggiornamento
8	\(-\)	20	1	20	1	\(v[8]\leftarrow 20\), \(s[8]\leftarrow 1\)
9	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
9	1	\(-\)	\(-\)	23	1	\(p[1]+v[7]=5+18=23>m=0\): \(m\leftarrow 23\), \(t\leftarrow 1\)
9	2	\(-\)	\(-\)	23	1	\(p[2]+v[6]=6+15=21\le m=23\): nessun aggiornamento
9	3	\(-\)	\(-\)	23	1	\(p[3]+v[3]=14+6=20\le m=23\): nessun aggiornamento
9	4	\(-\)	\(-\)	23	1	\(p[4]+v[2]=18+5=23\le m=23\): nessun aggiornamento
9	\(-\)	23	1	23	1	\(v[9]\leftarrow 23\), \(s[9]\leftarrow 1\)

Questo è il vettore \(v\) dopo l'esecuzione del primo algoritmo di PD:

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

Questo è il vettore \(s\) dopo l'esecuzione del primo algoritmo di PD:

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

Abbiamo il seguente vettore \(s\):

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

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

Iterazione	\(k\)	\(s[k]\)	\(x[1]\)	\(x[4]\)	Azione
-	-	-	0	0	\(k=9\)
1	9	1	1	0	\(x[1]\leftarrow 1\), \(k\leftarrow 9-2=7\)
2	7	4	1	1	\(x[4]\leftarrow 1\), \(k\leftarrow 7-7=0\)

Quindi il vettore

\[ (1,0,0,1) \]

è una soluzione ottima. Il valore ottimo è

\[ v[9]=23. \]

Esecuzione passo per passo del secondo 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. Tutte le celle della riga \(j=0\) sono inizializzate a \(0\).

\(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	\(k<w[1]\): \(v[1][0]\leftarrow v[0][0]=0\), \(s[1][0]\leftarrow 0\)
1	1	0	0	\(k<w[1]\): \(v[1][1]\leftarrow v[0][1]=0\), \(s[1][1]\leftarrow 0\)
1	2	5	1	\(p[1]+v[1][0]=5+0>v[0][2]=0\): \(v[1][2]\leftarrow 5\), \(s[1][2]\leftarrow 1\)
1	3	5	1	\(p[1]+v[1][1]=5+0>v[0][3]=0\): \(v[1][3]\leftarrow 5\), \(s[1][3]\leftarrow 1\)
1	4	10	1	\(p[1]+v[1][2]=5+5>v[0][4]=0\): \(v[1][4]\leftarrow 10\), \(s[1][4]\leftarrow 1\)
1	5	10	1	\(p[1]+v[1][3]=5+5>v[0][5]=0\): \(v[1][5]\leftarrow 10\), \(s[1][5]\leftarrow 1\)
1	6	15	1	\(p[1]+v[1][4]=5+10>v[0][6]=0\): \(v[1][6]\leftarrow 15\), \(s[1][6]\leftarrow 1\)
1	7	15	1	\(p[1]+v[1][5]=5+10>v[0][7]=0\): \(v[1][7]\leftarrow 15\), \(s[1][7]\leftarrow 1\)
1	8	20	1	\(p[1]+v[1][6]=5+15>v[0][8]=0\): \(v[1][8]\leftarrow 20\), \(s[1][8]\leftarrow 1\)
1	9	20	1	\(p[1]+v[1][7]=5+15>v[0][9]=0\): \(v[1][9]\leftarrow 20\), \(s[1][9]\leftarrow 1\)
2	0	0	0	\(k<w[2]\): \(v[2][0]\leftarrow v[1][0]=0\), \(s[2][0]\leftarrow 0\)
2	1	0	0	\(k<w[2]\): \(v[2][1]\leftarrow v[1][1]=0\), \(s[2][1]\leftarrow 0\)
2	2	5	0	\(k<w[2]\): \(v[2][2]\leftarrow v[1][2]=5\), \(s[2][2]\leftarrow 0\)
2	3	6	1	\(p[2]+v[2][0]=6+0>v[1][3]=5\): \(v[2][3]\leftarrow 6\), \(s[2][3]\leftarrow 1\)
2	4	10	0	\(p[2]+v[2][1]=6+0\le v[1][4]=10\): \(v[2][4]\leftarrow 10\), \(s[2][4]\leftarrow 0\)
2	5	11	1	\(p[2]+v[2][2]=6+5>v[1][5]=10\): \(v[2][5]\leftarrow 11\), \(s[2][5]\leftarrow 1\)
2	6	15	0	\(p[2]+v[2][3]=6+6\le v[1][6]=15\): \(v[2][6]\leftarrow 15\), \(s[2][6]\leftarrow 0\)
2	7	16	1	\(p[2]+v[2][4]=6+10>v[1][7]=15\): \(v[2][7]\leftarrow 16\), \(s[2][7]\leftarrow 1\)
2	8	20	0	\(p[2]+v[2][5]=6+11\le v[1][8]=20\): \(v[2][8]\leftarrow 20\), \(s[2][8]\leftarrow 0\)
2	9	21	1	\(p[2]+v[2][6]=6+15>v[1][9]=20\): \(v[2][9]\leftarrow 21\), \(s[2][9]\leftarrow 1\)
3	0	0	0	\(k<w[3]\): \(v[3][0]\leftarrow v[2][0]=0\), \(s[3][0]\leftarrow 0\)
3	1	0	0	\(k<w[3]\): \(v[3][1]\leftarrow v[2][1]=0\), \(s[3][1]\leftarrow 0\)
3	2	5	0	\(k<w[3]\): \(v[3][2]\leftarrow v[2][2]=5\), \(s[3][2]\leftarrow 0\)
3	3	6	0	\(k<w[3]\): \(v[3][3]\leftarrow v[2][3]=6\), \(s[3][3]\leftarrow 0\)
3	4	10	0	\(k<w[3]\): \(v[3][4]\leftarrow v[2][4]=10\), \(s[3][4]\leftarrow 0\)
3	5	11	0	\(k<w[3]\): \(v[3][5]\leftarrow v[2][5]=11\), \(s[3][5]\leftarrow 0\)
3	6	15	0	\(p[3]+v[3][0]=14+0\le v[2][6]=15\): \(v[3][6]\leftarrow 15\), \(s[3][6]\leftarrow 0\)
3	7	16	0	\(p[3]+v[3][1]=14+0\le v[2][7]=16\): \(v[3][7]\leftarrow 16\), \(s[3][7]\leftarrow 0\)
3	8	20	0	\(p[3]+v[3][2]=14+5\le v[2][8]=20\): \(v[3][8]\leftarrow 20\), \(s[3][8]\leftarrow 0\)
3	9	21	0	\(p[3]+v[3][3]=14+6\le v[2][9]=21\): \(v[3][9]\leftarrow 21\), \(s[3][9]\leftarrow 0\)
4	0	0	0	\(k<w[4]\): \(v[4][0]\leftarrow v[3][0]=0\), \(s[4][0]\leftarrow 0\)
4	1	0	0	\(k<w[4]\): \(v[4][1]\leftarrow v[3][1]=0\), \(s[4][1]\leftarrow 0\)
4	2	5	0	\(k<w[4]\): \(v[4][2]\leftarrow v[3][2]=5\), \(s[4][2]\leftarrow 0\)
4	3	6	0	\(k<w[4]\): \(v[4][3]\leftarrow v[3][3]=6\), \(s[4][3]\leftarrow 0\)
4	4	10	0	\(k<w[4]\): \(v[4][4]\leftarrow v[3][4]=10\), \(s[4][4]\leftarrow 0\)
4	5	11	0	\(k<w[4]\): \(v[4][5]\leftarrow v[3][5]=11\), \(s[4][5]\leftarrow 0\)
4	6	15	0	\(k<w[4]\): \(v[4][6]\leftarrow v[3][6]=15\), \(s[4][6]\leftarrow 0\)
4	7	18	1	\(p[4]+v[4][0]=18+0>v[3][7]=16\): \(v[4][7]\leftarrow 18\), \(s[4][7]\leftarrow 1\)
4	8	20	0	\(p[4]+v[4][1]=18+0\le v[3][8]=20\): \(v[4][8]\leftarrow 20\), \(s[4][8]\leftarrow 0\)
4	9	23	1	\(p[4]+v[4][2]=18+5>v[3][9]=21\): \(v[4][9]\leftarrow 23\), \(s[4][9]\leftarrow 1\)

Questa è la matrice \(v\) dopo l'esecuzione del secondo 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 & 5 & 5 & 10 & 10 & 15 & 15 & 20 & 20 \\ {j=2} & 0 & 0 & 5 & 6 & 10 & 11 & 15 & 16 & 20 & 21 \\ {j=3} & 0 & 0 & 5 & 6 & 10 & 11 & 15 & 16 & 20 & 21 \\ {j=4} & 0 & 0 & 5 & 6 & 10 & 11 & 15 & 18 & 20 & 23 \\ \hline \end{array} \]

Questa è la matrice \(s\) dopo l'esecuzione del secondo 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array} \]

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

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

Quindi il vettore

\[ (1,0,0,1) \]

è una soluzione ottima. Il valore ottimo è

\[ v[4][9]=23. \]

Esercizio 18.5: I due algoritmi di PD per l'UKP (5 tipi di oggetto, \(c=11\))

Consideriamo la seguente istanza dell'UKP, in cui lo zaino ha capacità \(c=11\), ogni tipo di oggetto è disponibile in infinite copie e i profitti e i pesi dei tipi di oggetto sono:

\[ \begin{array}{l|rrrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\ \hline {p_j} & 3 & 9 & 10 & 16 & 17 \\ {w_j} & 2 & 5 & 6 & 9 & 10 \\ \hline \end{array} \]

Domande

Mostrare l'esecuzione del primo algoritmo di PD bottom-up riportando, per ogni iterazione, i valori del vettore \(v\) e i valori del vettore \(s\).
Usando il vettore \(s\), ricostruire una soluzione ottima in notazione intera \((x_1,x_2,\dots,x_n)\) e riportare il valore ottimo.
Mostrare l'esecuzione del secondo 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,\dots,x_n)\) e riportare il valore ottimo.

Soluzione

Esecuzione passo per passo del primo algoritmo di PD bottom-up

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

\(k\)	\(j\)	\(v[k]\)	\(s[k]\)	\(m\)	\(t\)	Azione
\(-\)	\(-\)	0	\(-\)	\(-\)	\(-\)	\(v[0]\leftarrow 0\)
1	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
1	1	\(-\)	\(-\)	0	0	\(w[1]=2>k=1\): nessun aggiornamento
1	2	\(-\)	\(-\)	0	0	\(w[2]=5>k=1\): nessun aggiornamento
1	3	\(-\)	\(-\)	0	0	\(w[3]=6>k=1\): nessun aggiornamento
1	4	\(-\)	\(-\)	0	0	\(w[4]=9>k=1\): nessun aggiornamento
1	5	\(-\)	\(-\)	0	0	\(w[5]=10>k=1\): nessun aggiornamento
1	\(-\)	0	0	0	0	\(v[1]\leftarrow 0\), \(s[1]\leftarrow 0\)
2	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
2	1	\(-\)	\(-\)	3	1	\(p[1]+v[0]=3+0=3>m=0\): \(m\leftarrow 3\), \(t\leftarrow 1\)
2	2	\(-\)	\(-\)	3	1	\(w[2]=5>k=2\): nessun aggiornamento
2	3	\(-\)	\(-\)	3	1	\(w[3]=6>k=2\): nessun aggiornamento
2	4	\(-\)	\(-\)	3	1	\(w[4]=9>k=2\): nessun aggiornamento
2	5	\(-\)	\(-\)	3	1	\(w[5]=10>k=2\): nessun aggiornamento
2	\(-\)	3	1	3	1	\(v[2]\leftarrow 3\), \(s[2]\leftarrow 1\)
3	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
3	1	\(-\)	\(-\)	3	1	\(p[1]+v[1]=3+0=3>m=0\): \(m\leftarrow 3\), \(t\leftarrow 1\)
3	2	\(-\)	\(-\)	3	1	\(w[2]=5>k=3\): nessun aggiornamento
3	3	\(-\)	\(-\)	3	1	\(w[3]=6>k=3\): nessun aggiornamento
3	4	\(-\)	\(-\)	3	1	\(w[4]=9>k=3\): nessun aggiornamento
3	5	\(-\)	\(-\)	3	1	\(w[5]=10>k=3\): nessun aggiornamento
3	\(-\)	3	1	3	1	\(v[3]\leftarrow 3\), \(s[3]\leftarrow 1\)
4	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
4	1	\(-\)	\(-\)	6	1	\(p[1]+v[2]=3+3=6>m=0\): \(m\leftarrow 6\), \(t\leftarrow 1\)
4	2	\(-\)	\(-\)	6	1	\(w[2]=5>k=4\): nessun aggiornamento
4	3	\(-\)	\(-\)	6	1	\(w[3]=6>k=4\): nessun aggiornamento
4	4	\(-\)	\(-\)	6	1	\(w[4]=9>k=4\): nessun aggiornamento
4	5	\(-\)	\(-\)	6	1	\(w[5]=10>k=4\): nessun aggiornamento
4	\(-\)	6	1	6	1	\(v[4]\leftarrow 6\), \(s[4]\leftarrow 1\)
5	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
5	1	\(-\)	\(-\)	6	1	\(p[1]+v[3]=3+3=6>m=0\): \(m\leftarrow 6\), \(t\leftarrow 1\)
5	2	\(-\)	\(-\)	9	2	\(p[2]+v[0]=9+0=9>m=6\): \(m\leftarrow 9\), \(t\leftarrow 2\)
5	3	\(-\)	\(-\)	9	2	\(w[3]=6>k=5\): nessun aggiornamento
5	4	\(-\)	\(-\)	9	2	\(w[4]=9>k=5\): nessun aggiornamento
5	5	\(-\)	\(-\)	9	2	\(w[5]=10>k=5\): nessun aggiornamento
5	\(-\)	9	2	9	2	\(v[5]\leftarrow 9\), \(s[5]\leftarrow 2\)
6	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
6	1	\(-\)	\(-\)	9	1	\(p[1]+v[4]=3+6=9>m=0\): \(m\leftarrow 9\), \(t\leftarrow 1\)
6	2	\(-\)	\(-\)	9	1	\(p[2]+v[1]=9+0=9\le m=9\): nessun aggiornamento
6	3	\(-\)	\(-\)	10	3	\(p[3]+v[0]=10+0=10>m=9\): \(m\leftarrow 10\), \(t\leftarrow 3\)
6	4	\(-\)	\(-\)	10	3	\(w[4]=9>k=6\): nessun aggiornamento
6	5	\(-\)	\(-\)	10	3	\(w[5]=10>k=6\): nessun aggiornamento
6	\(-\)	10	3	10	3	\(v[6]\leftarrow 10\), \(s[6]\leftarrow 3\)
7	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
7	1	\(-\)	\(-\)	12	1	\(p[1]+v[5]=3+9=12>m=0\): \(m\leftarrow 12\), \(t\leftarrow 1\)
7	2	\(-\)	\(-\)	12	1	\(p[2]+v[2]=9+3=12\le m=12\): nessun aggiornamento
7	3	\(-\)	\(-\)	12	1	\(p[3]+v[1]=10+0=10\le m=12\): nessun aggiornamento
7	4	\(-\)	\(-\)	12	1	\(w[4]=9>k=7\): nessun aggiornamento
7	5	\(-\)	\(-\)	12	1	\(w[5]=10>k=7\): nessun aggiornamento
7	\(-\)	12	1	12	1	\(v[7]\leftarrow 12\), \(s[7]\leftarrow 1\)
8	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
8	1	\(-\)	\(-\)	13	1	\(p[1]+v[6]=3+10=13>m=0\): \(m\leftarrow 13\), \(t\leftarrow 1\)
8	2	\(-\)	\(-\)	13	1	\(p[2]+v[3]=9+3=12\le m=13\): nessun aggiornamento
8	3	\(-\)	\(-\)	13	1	\(p[3]+v[2]=10+3=13\le m=13\): nessun aggiornamento
8	4	\(-\)	\(-\)	13	1	\(w[4]=9>k=8\): nessun aggiornamento
8	5	\(-\)	\(-\)	13	1	\(w[5]=10>k=8\): nessun aggiornamento
8	\(-\)	13	1	13	1	\(v[8]\leftarrow 13\), \(s[8]\leftarrow 1\)
9	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
9	1	\(-\)	\(-\)	15	1	\(p[1]+v[7]=3+12=15>m=0\): \(m\leftarrow 15\), \(t\leftarrow 1\)
9	2	\(-\)	\(-\)	15	1	\(p[2]+v[4]=9+6=15\le m=15\): nessun aggiornamento
9	3	\(-\)	\(-\)	15	1	\(p[3]+v[3]=10+3=13\le m=15\): nessun aggiornamento
9	4	\(-\)	\(-\)	16	4	\(p[4]+v[0]=16+0=16>m=15\): \(m\leftarrow 16\), \(t\leftarrow 4\)
9	5	\(-\)	\(-\)	16	4	\(w[5]=10>k=9\): nessun aggiornamento
9	\(-\)	16	4	16	4	\(v[9]\leftarrow 16\), \(s[9]\leftarrow 4\)
10	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
10	1	\(-\)	\(-\)	16	1	\(p[1]+v[8]=3+13=16>m=0\): \(m\leftarrow 16\), \(t\leftarrow 1\)
10	2	\(-\)	\(-\)	18	2	\(p[2]+v[5]=9+9=18>m=16\): \(m\leftarrow 18\), \(t\leftarrow 2\)
10	3	\(-\)	\(-\)	18	2	\(p[3]+v[4]=10+6=16\le m=18\): nessun aggiornamento
10	4	\(-\)	\(-\)	18	2	\(p[4]+v[1]=16+0=16\le m=18\): nessun aggiornamento
10	5	\(-\)	\(-\)	18	2	\(p[5]+v[0]=17+0=17\le m=18\): nessun aggiornamento
10	\(-\)	18	2	18	2	\(v[10]\leftarrow 18\), \(s[10]\leftarrow 2\)
11	\(-\)	\(-\)	\(-\)	0	0	\(m\leftarrow 0\), \(t\leftarrow 0\)
11	1	\(-\)	\(-\)	19	1	\(p[1]+v[9]=3+16=19>m=0\): \(m\leftarrow 19\), \(t\leftarrow 1\)
11	2	\(-\)	\(-\)	19	1	\(p[2]+v[6]=9+10=19\le m=19\): nessun aggiornamento
11	3	\(-\)	\(-\)	19	1	\(p[3]+v[5]=10+9=19\le m=19\): nessun aggiornamento
11	4	\(-\)	\(-\)	19	1	\(p[4]+v[2]=16+3=19\le m=19\): nessun aggiornamento
11	5	\(-\)	\(-\)	19	1	\(p[5]+v[1]=17+0=17\le m=19\): nessun aggiornamento
11	\(-\)	19	1	19	1	\(v[11]\leftarrow 19\), \(s[11]\leftarrow 1\)

Questo è il vettore \(v\) dopo l'esecuzione del primo algoritmo di PD:

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

Questo è il vettore \(s\) dopo l'esecuzione del primo algoritmo di PD:

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

Abbiamo il seguente vettore \(s\):

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

Possiamo ricostruire una soluzione ottima partendo da \(k=11\) come segue:

Iterazione	\(k\)	\(s[k]\)	\(x[1]\)	\(x[4]\)	Azione
-	-	-	0	0	\(k=11\)
1	11	1	1	0	\(x[1]\leftarrow 1\), \(k\leftarrow 11-2=9\)
2	9	4	1	1	\(x[4]\leftarrow 1\), \(k\leftarrow 9-9=0\)

Quindi il vettore

\[ (1,0,0,1,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[11]=19. \]

Esecuzione passo per passo del secondo 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. Tutte le celle della riga \(j=0\) sono inizializzate a \(0\).

\(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\)
0	10	0	0	\(v[0][10]\leftarrow 0\), \(s[0][10]\leftarrow 0\)
0	11	0	0	\(v[0][11]\leftarrow 0\), \(s[0][11]\leftarrow 0\)
1	0	0	0	\(k<w[1]\): \(v[1][0]\leftarrow v[0][0]=0\), \(s[1][0]\leftarrow 0\)
1	1	0	0	\(k<w[1]\): \(v[1][1]\leftarrow v[0][1]=0\), \(s[1][1]\leftarrow 0\)
1	2	3	1	\(p[1]+v[1][0]=3+0>v[0][2]=0\): \(v[1][2]\leftarrow 3\), \(s[1][2]\leftarrow 1\)
1	3	3	1	\(p[1]+v[1][1]=3+0>v[0][3]=0\): \(v[1][3]\leftarrow 3\), \(s[1][3]\leftarrow 1\)
1	4	6	1	\(p[1]+v[1][2]=3+3>v[0][4]=0\): \(v[1][4]\leftarrow 6\), \(s[1][4]\leftarrow 1\)
1	5	6	1	\(p[1]+v[1][3]=3+3>v[0][5]=0\): \(v[1][5]\leftarrow 6\), \(s[1][5]\leftarrow 1\)
1	6	9	1	\(p[1]+v[1][4]=3+6>v[0][6]=0\): \(v[1][6]\leftarrow 9\), \(s[1][6]\leftarrow 1\)
1	7	9	1	\(p[1]+v[1][5]=3+6>v[0][7]=0\): \(v[1][7]\leftarrow 9\), \(s[1][7]\leftarrow 1\)
1	8	12	1	\(p[1]+v[1][6]=3+9>v[0][8]=0\): \(v[1][8]\leftarrow 12\), \(s[1][8]\leftarrow 1\)
1	9	12	1	\(p[1]+v[1][7]=3+9>v[0][9]=0\): \(v[1][9]\leftarrow 12\), \(s[1][9]\leftarrow 1\)
1	10	15	1	\(p[1]+v[1][8]=3+12>v[0][10]=0\): \(v[1][10]\leftarrow 15\), \(s[1][10]\leftarrow 1\)
1	11	15	1	\(p[1]+v[1][9]=3+12>v[0][11]=0\): \(v[1][11]\leftarrow 15\), \(s[1][11]\leftarrow 1\)
2	0	0	0	\(k<w[2]\): \(v[2][0]\leftarrow v[1][0]=0\), \(s[2][0]\leftarrow 0\)
2	1	0	0	\(k<w[2]\): \(v[2][1]\leftarrow v[1][1]=0\), \(s[2][1]\leftarrow 0\)
2	2	3	0	\(k<w[2]\): \(v[2][2]\leftarrow v[1][2]=3\), \(s[2][2]\leftarrow 0\)
2	3	3	0	\(k<w[2]\): \(v[2][3]\leftarrow v[1][3]=3\), \(s[2][3]\leftarrow 0\)
2	4	6	0	\(k<w[2]\): \(v[2][4]\leftarrow v[1][4]=6\), \(s[2][4]\leftarrow 0\)
2	5	9	1	\(p[2]+v[2][0]=9+0>v[1][5]=6\): \(v[2][5]\leftarrow 9\), \(s[2][5]\leftarrow 1\)
2	6	9	0	\(p[2]+v[2][1]=9+0\le v[1][6]=9\): \(v[2][6]\leftarrow 9\), \(s[2][6]\leftarrow 0\)
2	7	12	1	\(p[2]+v[2][2]=9+3>v[1][7]=9\): \(v[2][7]\leftarrow 12\), \(s[2][7]\leftarrow 1\)
2	8	12	0	\(p[2]+v[2][3]=9+3\le v[1][8]=12\): \(v[2][8]\leftarrow 12\), \(s[2][8]\leftarrow 0\)
2	9	15	1	\(p[2]+v[2][4]=9+6>v[1][9]=12\): \(v[2][9]\leftarrow 15\), \(s[2][9]\leftarrow 1\)
2	10	18	1	\(p[2]+v[2][5]=9+9>v[1][10]=15\): \(v[2][10]\leftarrow 18\), \(s[2][10]\leftarrow 1\)
2	11	18	1	\(p[2]+v[2][6]=9+9>v[1][11]=15\): \(v[2][11]\leftarrow 18\), \(s[2][11]\leftarrow 1\)
3	0	0	0	\(k<w[3]\): \(v[3][0]\leftarrow v[2][0]=0\), \(s[3][0]\leftarrow 0\)
3	1	0	0	\(k<w[3]\): \(v[3][1]\leftarrow v[2][1]=0\), \(s[3][1]\leftarrow 0\)
3	2	3	0	\(k<w[3]\): \(v[3][2]\leftarrow v[2][2]=3\), \(s[3][2]\leftarrow 0\)
3	3	3	0	\(k<w[3]\): \(v[3][3]\leftarrow v[2][3]=3\), \(s[3][3]\leftarrow 0\)
3	4	6	0	\(k<w[3]\): \(v[3][4]\leftarrow v[2][4]=6\), \(s[3][4]\leftarrow 0\)
3	5	9	0	\(k<w[3]\): \(v[3][5]\leftarrow v[2][5]=9\), \(s[3][5]\leftarrow 0\)
3	6	10	1	\(p[3]+v[3][0]=10+0>v[2][6]=9\): \(v[3][6]\leftarrow 10\), \(s[3][6]\leftarrow 1\)
3	7	12	0	\(p[3]+v[3][1]=10+0\le v[2][7]=12\): \(v[3][7]\leftarrow 12\), \(s[3][7]\leftarrow 0\)
3	8	13	1	\(p[3]+v[3][2]=10+3>v[2][8]=12\): \(v[3][8]\leftarrow 13\), \(s[3][8]\leftarrow 1\)
3	9	15	0	\(p[3]+v[3][3]=10+3\le v[2][9]=15\): \(v[3][9]\leftarrow 15\), \(s[3][9]\leftarrow 0\)
3	10	18	0	\(p[3]+v[3][4]=10+6\le v[2][10]=18\): \(v[3][10]\leftarrow 18\), \(s[3][10]\leftarrow 0\)
3	11	19	1	\(p[3]+v[3][5]=10+9>v[2][11]=18\): \(v[3][11]\leftarrow 19\), \(s[3][11]\leftarrow 1\)
4	0	0	0	\(k<w[4]\): \(v[4][0]\leftarrow v[3][0]=0\), \(s[4][0]\leftarrow 0\)
4	1	0	0	\(k<w[4]\): \(v[4][1]\leftarrow v[3][1]=0\), \(s[4][1]\leftarrow 0\)
4	2	3	0	\(k<w[4]\): \(v[4][2]\leftarrow v[3][2]=3\), \(s[4][2]\leftarrow 0\)
4	3	3	0	\(k<w[4]\): \(v[4][3]\leftarrow v[3][3]=3\), \(s[4][3]\leftarrow 0\)
4	4	6	0	\(k<w[4]\): \(v[4][4]\leftarrow v[3][4]=6\), \(s[4][4]\leftarrow 0\)
4	5	9	0	\(k<w[4]\): \(v[4][5]\leftarrow v[3][5]=9\), \(s[4][5]\leftarrow 0\)
4	6	10	0	\(k<w[4]\): \(v[4][6]\leftarrow v[3][6]=10\), \(s[4][6]\leftarrow 0\)
4	7	12	0	\(k<w[4]\): \(v[4][7]\leftarrow v[3][7]=12\), \(s[4][7]\leftarrow 0\)
4	8	13	0	\(k<w[4]\): \(v[4][8]\leftarrow v[3][8]=13\), \(s[4][8]\leftarrow 0\)
4	9	16	1	\(p[4]+v[4][0]=16+0>v[3][9]=15\): \(v[4][9]\leftarrow 16\), \(s[4][9]\leftarrow 1\)
4	10	18	0	\(p[4]+v[4][1]=16+0\le v[3][10]=18\): \(v[4][10]\leftarrow 18\), \(s[4][10]\leftarrow 0\)
4	11	19	0	\(p[4]+v[4][2]=16+3\le v[3][11]=19\): \(v[4][11]\leftarrow 19\), \(s[4][11]\leftarrow 0\)
5	0	0	0	\(k<w[5]\): \(v[5][0]\leftarrow v[4][0]=0\), \(s[5][0]\leftarrow 0\)
5	1	0	0	\(k<w[5]\): \(v[5][1]\leftarrow v[4][1]=0\), \(s[5][1]\leftarrow 0\)
5	2	3	0	\(k<w[5]\): \(v[5][2]\leftarrow v[4][2]=3\), \(s[5][2]\leftarrow 0\)
5	3	3	0	\(k<w[5]\): \(v[5][3]\leftarrow v[4][3]=3\), \(s[5][3]\leftarrow 0\)
5	4	6	0	\(k<w[5]\): \(v[5][4]\leftarrow v[4][4]=6\), \(s[5][4]\leftarrow 0\)
5	5	9	0	\(k<w[5]\): \(v[5][5]\leftarrow v[4][5]=9\), \(s[5][5]\leftarrow 0\)
5	6	10	0	\(k<w[5]\): \(v[5][6]\leftarrow v[4][6]=10\), \(s[5][6]\leftarrow 0\)
5	7	12	0	\(k<w[5]\): \(v[5][7]\leftarrow v[4][7]=12\), \(s[5][7]\leftarrow 0\)
5	8	13	0	\(k<w[5]\): \(v[5][8]\leftarrow v[4][8]=13\), \(s[5][8]\leftarrow 0\)
5	9	16	0	\(k<w[5]\): \(v[5][9]\leftarrow v[4][9]=16\), \(s[5][9]\leftarrow 0\)
5	10	18	0	\(p[5]+v[5][0]=17+0\le v[4][10]=18\): \(v[5][10]\leftarrow 18\), \(s[5][10]\leftarrow 0\)
5	11	19	0	\(p[5]+v[5][1]=17+0\le v[4][11]=19\): \(v[5][11]\leftarrow 19\), \(s[5][11]\leftarrow 0\)

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

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

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

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

Abbiamo la seguente matrice \(s\):

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

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

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

Quindi il vettore

\[ (0,1,1,0,0) \]

è una soluzione ottima. Il valore ottimo è

\[ v[5][11]=19. \]

La soluzione ottima non è unica e i due algoritmi di PD ne trovano due diverse: il primo trova \((1,0,0,1,0)\), con peso totale \(2+9=11\) e profitto totale \(3+16=19\); il secondo trova \((0,1,1,0,0)\), con peso totale \(5+6=11\) e profitto totale \(9+10=19\). Queste sono le sole due soluzioni ottime.