Esercizi · PD per il problema del subset sum¶

Esercizi · Capitolo 20 · ogni soluzione si apre con un clic · Capitolo 20: Subset sum (SSP) · Eserciziario, volume 3 (PDF)

Ricorrenza usata in questi esercizi

L'algoritmo di PD del capitolo «PD per il problema del subset sum»: $r(j,k)\in\{\textit{true},\textit{false}\}$ dice se il valore obiettivo $k$ è il peso totale di un sottoinsieme degli oggetti $1,2,\dots,j$, e

\[ r(j,k)= \left\{ \begin{array}{ll} \textit{true} & \textrm{se $k=0$,}\\[2ex] \textit{false} & \textrm{se $j=0$ e $k\ge 1$,}\\[2ex] r(j-1,k) & \textrm{se $j,k\ge 1$ e $w_j>k$,}\\[2ex] r(j-1,k) \,\lor\, r(j-1,k-w_j) & \textrm{se $j,k\ge 1$ e $w_j\le k$.} \end{array} \right. \]

La risposta è $r(n,c)$. La matrice $s$ memorizza $s[j][k]=1$ se l'oggetto $j$ è usato, cioè se $r[j-1][k]$ è false e $r[j-1][k-w_j]$ è true; un sottoinsieme si ricostruisce da $j=n$ e $k=c$ con $x_j\leftarrow s[j][k]$, $k\leftarrow k-s[j][k]\,w_j$.

Esercizio 20.1: Esercizio 1: problema del subset sum

Consideriamo la seguente istanza dell'SSP, con valore obiettivo $c=7$ e $3$ oggetti di pesi:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni passo, le celle $r[j][k]$ e $s[j][k]$; poi scrivere le matrici $r$ e $s$.
Dare la risposta all'istanza dell'SSP e, se è sì, ricostruire dalla matrice $s$ un sottoinsieme di peso totale $c$, come vettore binario $(x_1,x_2,x_3)$.
Usando l'ultima riga della matrice $r$, elencare tutti i valori obiettivo $k\in\{1,2,\dots,7\}$ raggiungibili con i 3 oggetti.

Soluzione

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

Esecuzione passo per passo dell'algoritmo di PD bottom-up. La riga $j=0$ è $r[0][0]=\mathrm{T}$ e $r[0][k]=\mathrm{F}$ per $k\ge 1$, con $s[0][k]=0$; $\mathrm{T}$ sta per true e $\mathrm{F}$ per false. L'oggetto $j$ è usato ($s[j][k]=1$) solo se $r[j-1][k]$ è $\mathrm{F}$.

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$1$	$0$	$\mathrm{T}$	$0$	$w_1=2>0$: $r[0][0]=\mathrm{T}$
$1$	$1$	$\mathrm{F}$	$0$	$w_1=2>1$: $r[0][1]=\mathrm{F}$
$1$	$2$	$\mathrm{T}$	$1$	$r[0][2]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$1$	$3$	$\mathrm{F}$	$0$	$r[0][3]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$4$	$\mathrm{F}$	$0$	$r[0][4]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$5$	$\mathrm{F}$	$0$	$r[0][5]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$6$	$\mathrm{F}$	$0$	$r[0][6]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$7$	$\mathrm{F}$	$0$	$r[0][7]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$0$	$\mathrm{T}$	$0$	$w_2=3>0$: $r[1][0]=\mathrm{T}$
$2$	$1$	$\mathrm{F}$	$0$	$w_2=3>1$: $r[1][1]=\mathrm{F}$
$2$	$2$	$\mathrm{T}$	$0$	$w_2=3>2$: $r[1][2]=\mathrm{T}$
$2$	$3$	$\mathrm{T}$	$1$	$r[1][3]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$4$	$\mathrm{F}$	$0$	$r[1][4]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$5$	$\mathrm{T}$	$1$	$r[1][5]\lor r[1][2]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$6$	$\mathrm{F}$	$0$	$r[1][6]\lor r[1][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$7$	$\mathrm{F}$	$0$	$r[1][7]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$3$	$0$	$\mathrm{T}$	$0$	$w_3=5>0$: $r[2][0]=\mathrm{T}$
$3$	$1$	$\mathrm{F}$	$0$	$w_3=5>1$: $r[2][1]=\mathrm{F}$
$3$	$2$	$\mathrm{T}$	$0$	$w_3=5>2$: $r[2][2]=\mathrm{T}$
$3$	$3$	$\mathrm{T}$	$0$	$w_3=5>3$: $r[2][3]=\mathrm{T}$
$3$	$4$	$\mathrm{F}$	$0$	$w_3=5>4$: $r[2][4]=\mathrm{F}$
$3$	$5$	$\mathrm{T}$	$0$	$r[2][5]\lor r[2][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}$
$3$	$6$	$\mathrm{F}$	$0$	$r[2][6]\lor r[2][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$3$	$7$	$\mathrm{T}$	$1$	$r[2][7]\lor r[2][2]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$

Questa è la matrice $r$ dopo l'esecuzione dell'algoritmo di PD:

\[ \begin{array}{l|rrrrrrrr} \hline {r[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=1} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=2} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=3} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} \\ \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} & {0} & {1} & {0} & {0} & {0} & {0} & {0} \\ {j=2} & {0} & {0} & {0} & {1} & {0} & {1} & {0} & {0} \\ {j=3} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} \\ \hline \end{array} \]

Poiché $r[3][7]=\mathrm{T}$, la risposta è sì. Partendo da $j=3$ e $k=7$:

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

Il vettore $(1,0,1)$ seleziona il sottoinsieme $\{1,3\}$, di peso totale $2+5=7=c$. È l'unico sottoinsieme con peso totale $7$.

L'ultima riga $r[3][\cdot]$ è $\mathrm{T}$ esattamente per $k\in\{2,3,5,7\}$: questi sono i valori obiettivo raggiungibili. Gli altri valori in $\{1,2,\dots,7\}$ non sono il peso totale di alcun sottoinsieme.

Esercizio 20.2: Esercizio 2: problema del subset sum

Consideriamo la seguente istanza dell'SSP, con valore obiettivo $c=9$ e $3$ oggetti di pesi:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni passo, le celle $r[j][k]$ e $s[j][k]$; poi scrivere le matrici $r$ e $s$.
Dare la risposta all'istanza dell'SSP e, se è sì, ricostruire dalla matrice $s$ un sottoinsieme di peso totale $c$, come vettore binario $(x_1,x_2,x_3)$.
Usando l'ultima riga della matrice $r$, elencare tutti i valori obiettivo $k\in\{1,2,\dots,9\}$ raggiungibili con i 3 oggetti.

Soluzione

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

Esecuzione passo per passo dell'algoritmo di PD bottom-up. La riga $j=0$ è $r[0][0]=\mathrm{T}$ e $r[0][k]=\mathrm{F}$ per $k\ge 1$, con $s[0][k]=0$; $\mathrm{T}$ sta per true e $\mathrm{F}$ per false. L'oggetto $j$ è usato ($s[j][k]=1$) solo se $r[j-1][k]$ è $\mathrm{F}$.

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$1$	$0$	$\mathrm{T}$	$0$	$w_1=3>0$: $r[0][0]=\mathrm{T}$
$1$	$1$	$\mathrm{F}$	$0$	$w_1=3>1$: $r[0][1]=\mathrm{F}$
$1$	$2$	$\mathrm{F}$	$0$	$w_1=3>2$: $r[0][2]=\mathrm{F}$
$1$	$3$	$\mathrm{T}$	$1$	$r[0][3]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$1$	$4$	$\mathrm{F}$	$0$	$r[0][4]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$5$	$\mathrm{F}$	$0$	$r[0][5]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$6$	$\mathrm{F}$	$0$	$r[0][6]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$7$	$\mathrm{F}$	$0$	$r[0][7]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$8$	$\mathrm{F}$	$0$	$r[0][8]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$9$	$\mathrm{F}$	$0$	$r[0][9]\lor r[0][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$0$	$\mathrm{T}$	$0$	$w_2=4>0$: $r[1][0]=\mathrm{T}$
$2$	$1$	$\mathrm{F}$	$0$	$w_2=4>1$: $r[1][1]=\mathrm{F}$
$2$	$2$	$\mathrm{F}$	$0$	$w_2=4>2$: $r[1][2]=\mathrm{F}$
$2$	$3$	$\mathrm{T}$	$0$	$w_2=4>3$: $r[1][3]=\mathrm{T}$
$2$	$4$	$\mathrm{T}$	$1$	$r[1][4]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$5$	$\mathrm{F}$	$0$	$r[1][5]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$6$	$\mathrm{F}$	$0$	$r[1][6]\lor r[1][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$7$	$\mathrm{T}$	$1$	$r[1][7]\lor r[1][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$8$	$\mathrm{F}$	$0$	$r[1][8]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$9$	$\mathrm{F}$	$0$	$r[1][9]\lor r[1][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$3$	$0$	$\mathrm{T}$	$0$	$w_3=6>0$: $r[2][0]=\mathrm{T}$
$3$	$1$	$\mathrm{F}$	$0$	$w_3=6>1$: $r[2][1]=\mathrm{F}$
$3$	$2$	$\mathrm{F}$	$0$	$w_3=6>2$: $r[2][2]=\mathrm{F}$
$3$	$3$	$\mathrm{T}$	$0$	$w_3=6>3$: $r[2][3]=\mathrm{T}$
$3$	$4$	$\mathrm{T}$	$0$	$w_3=6>4$: $r[2][4]=\mathrm{T}$
$3$	$5$	$\mathrm{F}$	$0$	$w_3=6>5$: $r[2][5]=\mathrm{F}$
$3$	$6$	$\mathrm{T}$	$1$	$r[2][6]\lor r[2][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$3$	$7$	$\mathrm{T}$	$0$	$r[2][7]\lor r[2][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}$
$3$	$8$	$\mathrm{F}$	$0$	$r[2][8]\lor r[2][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$3$	$9$	$\mathrm{T}$	$1$	$r[2][9]\lor r[2][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$

Questa è la matrice $r$ dopo l'esecuzione dell'algoritmo di PD:

\[ \begin{array}{l|rrrrrrrrrr} \hline {r[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} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=1} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=2} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=3} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} \\ \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} & {0} & {0} & {0} & {0} & {0} & {0} \\ {j=2} & {0} & {0} & {0} & {0} & {1} & {0} & {0} & {1} & {0} & {0} \\ {j=3} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {0} & {0} & {1} \\ \hline \end{array} \]

Poiché $r[3][9]=\mathrm{T}$, la risposta è sì. Partendo da $j=3$ e $k=9$:

Iterazione	$j$	$k$	$s[j][k]$	$x[1]$	$x[3]$	Azione
$-$	$-$	$-$	$-$	0	0	$k=9$
$1$	$3$	$9$	$1$	0	1	$x[3]\leftarrow 1$, $k\leftarrow 9-6=3$
$2$	$2$	$3$	$0$	0	1	$x[2]\leftarrow 0$, $k=3$
$3$	$1$	$3$	$1$	1	1	$x[1]\leftarrow 1$, $k\leftarrow 3-3=0$

Il vettore $(1,0,1)$ seleziona il sottoinsieme $\{1,3\}$, di peso totale $3+6=9=c$. È l'unico sottoinsieme con peso totale $9$.

L'ultima riga $r[3][\cdot]$ è $\mathrm{T}$ esattamente per $k\in\{3,4,6,7,9\}$: questi sono i valori obiettivo raggiungibili. Gli altri valori in $\{1,2,\dots,9\}$ non sono il peso totale di alcun sottoinsieme.

Esercizio 20.3: Esercizio 3: problema del subset sum

Consideriamo la seguente istanza dell'SSP, con valore obiettivo $c=7$ e $3$ oggetti di pesi:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni passo, le celle $r[j][k]$ e $s[j][k]$; poi scrivere le matrici $r$ e $s$.
Dare la risposta all'istanza dell'SSP e, se è sì, ricostruire dalla matrice $s$ un sottoinsieme di peso totale $c$, come vettore binario $(x_1,x_2,x_3)$.
Usando l'ultima riga della matrice $r$, elencare tutti i valori obiettivo $k\in\{1,2,\dots,7\}$ raggiungibili con i 3 oggetti.

Soluzione

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

Esecuzione passo per passo dell'algoritmo di PD bottom-up. La riga $j=0$ è $r[0][0]=\mathrm{T}$ e $r[0][k]=\mathrm{F}$ per $k\ge 1$, con $s[0][k]=0$; $\mathrm{T}$ sta per true e $\mathrm{F}$ per false. L'oggetto $j$ è usato ($s[j][k]=1$) solo se $r[j-1][k]$ è $\mathrm{F}$.

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$1$	$0$	$\mathrm{T}$	$0$	$w_1=2>0$: $r[0][0]=\mathrm{T}$
$1$	$1$	$\mathrm{F}$	$0$	$w_1=2>1$: $r[0][1]=\mathrm{F}$
$1$	$2$	$\mathrm{T}$	$1$	$r[0][2]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$1$	$3$	$\mathrm{F}$	$0$	$r[0][3]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$4$	$\mathrm{F}$	$0$	$r[0][4]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$5$	$\mathrm{F}$	$0$	$r[0][5]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$6$	$\mathrm{F}$	$0$	$r[0][6]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$7$	$\mathrm{F}$	$0$	$r[0][7]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$0$	$\mathrm{T}$	$0$	$w_2=4>0$: $r[1][0]=\mathrm{T}$
$2$	$1$	$\mathrm{F}$	$0$	$w_2=4>1$: $r[1][1]=\mathrm{F}$
$2$	$2$	$\mathrm{T}$	$0$	$w_2=4>2$: $r[1][2]=\mathrm{T}$
$2$	$3$	$\mathrm{F}$	$0$	$w_2=4>3$: $r[1][3]=\mathrm{F}$
$2$	$4$	$\mathrm{T}$	$1$	$r[1][4]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$5$	$\mathrm{F}$	$0$	$r[1][5]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$6$	$\mathrm{T}$	$1$	$r[1][6]\lor r[1][2]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$7$	$\mathrm{F}$	$0$	$r[1][7]\lor r[1][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$3$	$0$	$\mathrm{T}$	$0$	$w_3=6>0$: $r[2][0]=\mathrm{T}$
$3$	$1$	$\mathrm{F}$	$0$	$w_3=6>1$: $r[2][1]=\mathrm{F}$
$3$	$2$	$\mathrm{T}$	$0$	$w_3=6>2$: $r[2][2]=\mathrm{T}$
$3$	$3$	$\mathrm{F}$	$0$	$w_3=6>3$: $r[2][3]=\mathrm{F}$
$3$	$4$	$\mathrm{T}$	$0$	$w_3=6>4$: $r[2][4]=\mathrm{T}$
$3$	$5$	$\mathrm{F}$	$0$	$w_3=6>5$: $r[2][5]=\mathrm{F}$
$3$	$6$	$\mathrm{T}$	$0$	$r[2][6]\lor r[2][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}$
$3$	$7$	$\mathrm{F}$	$0$	$r[2][7]\lor r[2][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$

Questa è la matrice $r$ dopo l'esecuzione dell'algoritmo di PD:

\[ \begin{array}{l|rrrrrrrr} \hline {r[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=1} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=2} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} \\ {j=3} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} \\ \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} & {0} & {1} & {0} & {0} & {0} & {0} & {0} \\ {j=2} & {0} & {0} & {0} & {0} & {1} & {0} & {1} & {0} \\ {j=3} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ \hline \end{array} \]

Poiché $r[3][7]=\mathrm{F}$, la risposta è no: nessun sottoinsieme degli oggetti ha peso totale $7$, e non c'è nulla da ricostruire. Infatti tutti i pesi $w=(2,4,6)$ sono pari, quindi ogni valore obiettivo raggiungibile è pari, mentre $c=7$ è dispari.
L'ultima riga $r[3][\cdot]$ è $\mathrm{T}$ esattamente per $k\in\{2,4,6\}$: questi sono i valori obiettivo raggiungibili. Gli altri valori in $\{1,2,\dots,7\}$ non sono il peso totale di alcun sottoinsieme.

Esercizio 20.4: Esercizio 4: problema del subset sum

Consideriamo la seguente istanza dell'SSP, con valore obiettivo $c=8$ e $4$ oggetti di pesi:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni passo, le celle $r[j][k]$ e $s[j][k]$; poi scrivere le matrici $r$ e $s$.
Dare la risposta all'istanza dell'SSP e, se è sì, ricostruire dalla matrice $s$ un sottoinsieme di peso totale $c$, come vettore binario $(x_1,x_2,x_3,x_4)$.
Usando l'ultima riga della matrice $r$, elencare tutti i valori obiettivo $k\in\{1,2,\dots,8\}$ raggiungibili con i 4 oggetti.

Soluzione

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

Esecuzione passo per passo dell'algoritmo di PD bottom-up. La riga $j=0$ è $r[0][0]=\mathrm{T}$ e $r[0][k]=\mathrm{F}$ per $k\ge 1$, con $s[0][k]=0$; $\mathrm{T}$ sta per true e $\mathrm{F}$ per false. L'oggetto $j$ è usato ($s[j][k]=1$) solo se $r[j-1][k]$ è $\mathrm{F}$.

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$1$	$0$	$\mathrm{T}$	$0$	$w_1=1>0$: $r[0][0]=\mathrm{T}$
$1$	$1$	$\mathrm{T}$	$1$	$r[0][1]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$1$	$2$	$\mathrm{F}$	$0$	$r[0][2]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$3$	$\mathrm{F}$	$0$	$r[0][3]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$4$	$\mathrm{F}$	$0$	$r[0][4]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$5$	$\mathrm{F}$	$0$	$r[0][5]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$6$	$\mathrm{F}$	$0$	$r[0][6]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$7$	$\mathrm{F}$	$0$	$r[0][7]\lor r[0][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$8$	$\mathrm{F}$	$0$	$r[0][8]\lor r[0][7]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$0$	$\mathrm{T}$	$0$	$w_2=4>0$: $r[1][0]=\mathrm{T}$
$2$	$1$	$\mathrm{T}$	$0$	$w_2=4>1$: $r[1][1]=\mathrm{T}$
$2$	$2$	$\mathrm{F}$	$0$	$w_2=4>2$: $r[1][2]=\mathrm{F}$
$2$	$3$	$\mathrm{F}$	$0$	$w_2=4>3$: $r[1][3]=\mathrm{F}$
$2$	$4$	$\mathrm{T}$	$1$	$r[1][4]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$5$	$\mathrm{T}$	$1$	$r[1][5]\lor r[1][1]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$6$	$\mathrm{F}$	$0$	$r[1][6]\lor r[1][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$7$	$\mathrm{F}$	$0$	$r[1][7]\lor r[1][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$8$	$\mathrm{F}$	$0$	$r[1][8]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$3$	$0$	$\mathrm{T}$	$0$	$w_3=5>0$: $r[2][0]=\mathrm{T}$
$3$	$1$	$\mathrm{T}$	$0$	$w_3=5>1$: $r[2][1]=\mathrm{T}$
$3$	$2$	$\mathrm{F}$	$0$	$w_3=5>2$: $r[2][2]=\mathrm{F}$
$3$	$3$	$\mathrm{F}$	$0$	$w_3=5>3$: $r[2][3]=\mathrm{F}$
$3$	$4$	$\mathrm{T}$	$0$	$w_3=5>4$: $r[2][4]=\mathrm{T}$
$3$	$5$	$\mathrm{T}$	$0$	$r[2][5]\lor r[2][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}$
$3$	$6$	$\mathrm{T}$	$1$	$r[2][6]\lor r[2][1]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$3$	$7$	$\mathrm{F}$	$0$	$r[2][7]\lor r[2][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$3$	$8$	$\mathrm{F}$	$0$	$r[2][8]\lor r[2][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$4$	$0$	$\mathrm{T}$	$0$	$w_4=7>0$: $r[3][0]=\mathrm{T}$
$4$	$1$	$\mathrm{T}$	$0$	$w_4=7>1$: $r[3][1]=\mathrm{T}$
$4$	$2$	$\mathrm{F}$	$0$	$w_4=7>2$: $r[3][2]=\mathrm{F}$
$4$	$3$	$\mathrm{F}$	$0$	$w_4=7>3$: $r[3][3]=\mathrm{F}$
$4$	$4$	$\mathrm{T}$	$0$	$w_4=7>4$: $r[3][4]=\mathrm{T}$
$4$	$5$	$\mathrm{T}$	$0$	$w_4=7>5$: $r[3][5]=\mathrm{T}$
$4$	$6$	$\mathrm{T}$	$0$	$w_4=7>6$: $r[3][6]=\mathrm{T}$
$4$	$7$	$\mathrm{T}$	$1$	$r[3][7]\lor r[3][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$4$	$8$	$\mathrm{T}$	$1$	$r[3][8]\lor r[3][1]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$

Questa è la matrice $r$ dopo l'esecuzione dell'algoritmo di PD:

\[ \begin{array}{l|rrrrrrrrr} \hline {r[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} \\ \hline {j=0} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=1} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=2} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=3} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=4} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} \\ \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} & {1} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {j=2} & {0} & {0} & {0} & {0} & {1} & {1} & {0} & {0} & {0} \\ {j=3} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {0} & {0} \\ {j=4} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {1} \\ \hline \end{array} \]

Poiché $r[4][8]=\mathrm{T}$, la risposta è sì. Partendo da $j=4$ e $k=8$:

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

Il vettore $(1,0,0,1)$ seleziona il sottoinsieme $\{1,4\}$, di peso totale $1+7=8=c$. È l'unico sottoinsieme con peso totale $8$.

L'ultima riga $r[4][\cdot]$ è $\mathrm{T}$ esattamente per $k\in\{1,4,5,6,7,8\}$: questi sono i valori obiettivo raggiungibili. Gli altri valori in $\{1,2,\dots,8\}$ non sono il peso totale di alcun sottoinsieme.

Esercizio 20.5: Esercizio 5: problema del subset sum

Consideriamo la seguente istanza dell'SSP, con valore obiettivo $c=8$ e $4$ oggetti di pesi:

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

Domande

Mostrare l'esecuzione dell'algoritmo di PD bottom-up riportando, per ogni passo, le celle $r[j][k]$ e $s[j][k]$; poi scrivere le matrici $r$ e $s$.
Dare la risposta all'istanza dell'SSP e, se è sì, ricostruire dalla matrice $s$ un sottoinsieme di peso totale $c$, come vettore binario $(x_1,x_2,x_3,x_4)$.
Usando l'ultima riga della matrice $r$, elencare tutti i valori obiettivo $k\in\{1,2,\dots,8\}$ raggiungibili con i 4 oggetti.

Soluzione

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

Esecuzione passo per passo dell'algoritmo di PD bottom-up. La riga $j=0$ è $r[0][0]=\mathrm{T}$ e $r[0][k]=\mathrm{F}$ per $k\ge 1$, con $s[0][k]=0$; $\mathrm{T}$ sta per true e $\mathrm{F}$ per false. L'oggetto $j$ è usato ($s[j][k]=1$) solo se $r[j-1][k]$ è $\mathrm{F}$.

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$1$	$0$	$\mathrm{T}$	$0$	$w_1=2>0$: $r[0][0]=\mathrm{T}$
$1$	$1$	$\mathrm{F}$	$0$	$w_1=2>1$: $r[0][1]=\mathrm{F}$
$1$	$2$	$\mathrm{T}$	$1$	$r[0][2]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$1$	$3$	$\mathrm{F}$	$0$	$r[0][3]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$4$	$\mathrm{F}$	$0$	$r[0][4]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$5$	$\mathrm{F}$	$0$	$r[0][5]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$6$	$\mathrm{F}$	$0$	$r[0][6]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$7$	$\mathrm{F}$	$0$	$r[0][7]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$8$	$\mathrm{F}$	$0$	$r[0][8]\lor r[0][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$0$	$\mathrm{T}$	$0$	$w_2=5>0$: $r[1][0]=\mathrm{T}$
$2$	$1$	$\mathrm{F}$	$0$	$w_2=5>1$: $r[1][1]=\mathrm{F}$
$2$	$2$	$\mathrm{T}$	$0$	$w_2=5>2$: $r[1][2]=\mathrm{T}$
$2$	$3$	$\mathrm{F}$	$0$	$w_2=5>3$: $r[1][3]=\mathrm{F}$
$2$	$4$	$\mathrm{F}$	$0$	$w_2=5>4$: $r[1][4]=\mathrm{F}$
$2$	$5$	$\mathrm{T}$	$1$	$r[1][5]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$6$	$\mathrm{F}$	$0$	$r[1][6]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$7$	$\mathrm{T}$	$1$	$r[1][7]\lor r[1][2]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$8$	$\mathrm{F}$	$0$	$r[1][8]\lor r[1][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$3$	$0$	$\mathrm{T}$	$0$	$w_3=6>0$: $r[2][0]=\mathrm{T}$
$3$	$1$	$\mathrm{F}$	$0$	$w_3=6>1$: $r[2][1]=\mathrm{F}$
$3$	$2$	$\mathrm{T}$	$0$	$w_3=6>2$: $r[2][2]=\mathrm{T}$
$3$	$3$	$\mathrm{F}$	$0$	$w_3=6>3$: $r[2][3]=\mathrm{F}$
$3$	$4$	$\mathrm{F}$	$0$	$w_3=6>4$: $r[2][4]=\mathrm{F}$
$3$	$5$	$\mathrm{T}$	$0$	$w_3=6>5$: $r[2][5]=\mathrm{T}$
$3$	$6$	$\mathrm{T}$	$1$	$r[2][6]\lor r[2][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$3$	$7$	$\mathrm{T}$	$0$	$r[2][7]\lor r[2][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}$
$3$	$8$	$\mathrm{T}$	$1$	$r[2][8]\lor r[2][2]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$4$	$0$	$\mathrm{T}$	$0$	$w_4=7>0$: $r[3][0]=\mathrm{T}$
$4$	$1$	$\mathrm{F}$	$0$	$w_4=7>1$: $r[3][1]=\mathrm{F}$
$4$	$2$	$\mathrm{T}$	$0$	$w_4=7>2$: $r[3][2]=\mathrm{T}$
$4$	$3$	$\mathrm{F}$	$0$	$w_4=7>3$: $r[3][3]=\mathrm{F}$
$4$	$4$	$\mathrm{F}$	$0$	$w_4=7>4$: $r[3][4]=\mathrm{F}$
$4$	$5$	$\mathrm{T}$	$0$	$w_4=7>5$: $r[3][5]=\mathrm{T}$
$4$	$6$	$\mathrm{T}$	$0$	$w_4=7>6$: $r[3][6]=\mathrm{T}$
$4$	$7$	$\mathrm{T}$	$0$	$r[3][7]\lor r[3][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}$
$4$	$8$	$\mathrm{T}$	$0$	$r[3][8]\lor r[3][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}$

Questa è la matrice $r$ dopo l'esecuzione dell'algoritmo di PD:

\[ \begin{array}{l|rrrrrrrrr} \hline {r[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} \\ \hline {j=0} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=1} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=2} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} \\ {j=3} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} \\ {j=4} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} \\ \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} & {0} & {0} & {0} & {0} & {0} & {0} \\ {j=2} & {0} & {0} & {0} & {0} & {0} & {1} & {0} & {1} & {0} \\ {j=3} & {0} & {0} & {0} & {0} & {0} & {0} & {1} & {0} & {1} \\ {j=4} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ \hline \end{array} \]

Poiché $r[4][8]=\mathrm{T}$, la risposta è sì. Partendo da $j=4$ e $k=8$:

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

Il vettore $(1,0,1,0)$ seleziona il sottoinsieme $\{1,3\}$, di peso totale $2+6=8=c$. È l'unico sottoinsieme con peso totale $8$.

L'ultima riga $r[4][\cdot]$ è $\mathrm{T}$ esattamente per $k\in\{2,5,6,7,8\}$: questi sono i valori obiettivo raggiungibili. Gli altri valori in $\{1,2,\dots,8\}$ non sono il peso totale di alcun sottoinsieme.

\(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Azione
\(1\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_1=2>0\): \(r[0][0]=\mathrm{T}\)
\(1\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_1=2>1\): \(r[0][1]=\mathrm{F}\)
\(1\)	\(2\)	\(\mathrm{T}\)	\(1\)	\(r[0][2]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(1\)	\(3\)	\(\mathrm{F}\)	\(0\)	\(r[0][3]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(r[0][4]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(5\)	\(\mathrm{F}\)	\(0\)	\(r[0][5]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[0][6]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(7\)	\(\mathrm{F}\)	\(0\)	\(r[0][7]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_2=3>0\): \(r[1][0]=\mathrm{T}\)
\(2\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_2=3>1\): \(r[1][1]=\mathrm{F}\)
\(2\)	\(2\)	\(\mathrm{T}\)	\(0\)	\(w_2=3>2\): \(r[1][2]=\mathrm{T}\)
\(2\)	\(3\)	\(\mathrm{T}\)	\(1\)	\(r[1][3]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(2\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(r[1][4]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(5\)	\(\mathrm{T}\)	\(1\)	\(r[1][5]\lor r[1][2]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(2\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[1][6]\lor r[1][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(7\)	\(\mathrm{F}\)	\(0\)	\(r[1][7]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)

\(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Azione
\(3\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_3=5>0\): \(r[2][0]=\mathrm{T}\)
\(3\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_3=5>1\): \(r[2][1]=\mathrm{F}\)
\(3\)	\(2\)	\(\mathrm{T}\)	\(0\)	\(w_3=5>2\): \(r[2][2]=\mathrm{T}\)
\(3\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_3=5>3\): \(r[2][3]=\mathrm{T}\)
\(3\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(w_3=5>4\): \(r[2][4]=\mathrm{F}\)
\(3\)	\(5\)	\(\mathrm{T}\)	\(0\)	\(r[2][5]\lor r[2][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}\)
\(3\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[2][6]\lor r[2][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(3\)	\(7\)	\(\mathrm{T}\)	\(1\)	\(r[2][7]\lor r[2][2]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)

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

\(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Azione
\(1\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_1=3>0\): \(r[0][0]=\mathrm{T}\)
\(1\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_1=3>1\): \(r[0][1]=\mathrm{F}\)
\(1\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_1=3>2\): \(r[0][2]=\mathrm{F}\)
\(1\)	\(3\)	\(\mathrm{T}\)	\(1\)	\(r[0][3]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(1\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(r[0][4]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(5\)	\(\mathrm{F}\)	\(0\)	\(r[0][5]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[0][6]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(7\)	\(\mathrm{F}\)	\(0\)	\(r[0][7]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(8\)	\(\mathrm{F}\)	\(0\)	\(r[0][8]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(9\)	\(\mathrm{F}\)	\(0\)	\(r[0][9]\lor r[0][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_2=4>0\): \(r[1][0]=\mathrm{T}\)
\(2\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_2=4>1\): \(r[1][1]=\mathrm{F}\)
\(2\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_2=4>2\): \(r[1][2]=\mathrm{F}\)
\(2\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_2=4>3\): \(r[1][3]=\mathrm{T}\)
\(2\)	\(4\)	\(\mathrm{T}\)	\(1\)	\(r[1][4]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(2\)	\(5\)	\(\mathrm{F}\)	\(0\)	\(r[1][5]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[1][6]\lor r[1][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(7\)	\(\mathrm{T}\)	\(1\)	\(r[1][7]\lor r[1][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(2\)	\(8\)	\(\mathrm{F}\)	\(0\)	\(r[1][8]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(9\)	\(\mathrm{F}\)	\(0\)	\(r[1][9]\lor r[1][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)

\(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Azione
\(3\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_3=6>0\): \(r[2][0]=\mathrm{T}\)
\(3\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_3=6>1\): \(r[2][1]=\mathrm{F}\)
\(3\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_3=6>2\): \(r[2][2]=\mathrm{F}\)
\(3\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_3=6>3\): \(r[2][3]=\mathrm{T}\)
\(3\)	\(4\)	\(\mathrm{T}\)	\(0\)	\(w_3=6>4\): \(r[2][4]=\mathrm{T}\)
\(3\)	\(5\)	\(\mathrm{F}\)	\(0\)	\(w_3=6>5\): \(r[2][5]=\mathrm{F}\)
\(3\)	\(6\)	\(\mathrm{T}\)	\(1\)	\(r[2][6]\lor r[2][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(3\)	\(7\)	\(\mathrm{T}\)	\(0\)	\(r[2][7]\lor r[2][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
\(3\)	\(8\)	\(\mathrm{F}\)	\(0\)	\(r[2][8]\lor r[2][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(3\)	\(9\)	\(\mathrm{T}\)	\(1\)	\(r[2][9]\lor r[2][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)