Exercises · DP for the subset sum problem

Exercises · Chapter 20 · each solution opens with a click · Chapter 20: Subset sum (SSP) · Exercises, volume 3 (PDF)

Recurrence used in these exercises

The DP algorithm of the chapter «DP for the subset sum problem»: \(r(j,k)\in\{\textit{true},\textit{false}\}\) tells whether the target value \(k\) is the total weight of a subset of the items \(1,2,\dots,j\), and

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

The answer is \(r(n,c)\). The matrix \(s\) stores \(s[j][k]=1\) if item \(j\) is used, that is, if \(r[j-1][k]\) is false and \(r[j-1][k-w_j]\) is true; a subset is reconstructed from \(j=n\) and \(k=c\) with \(x_j\leftarrow s[j][k]\), \(k\leftarrow k-s[j][k]\,w_j\).

Exercise 20.1: Exercise 1: Subset Sum Problem

Consider the following SSP instance, with target value \(c=7\) and \(3\) items with weights:

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

Questions

1. Show the execution of the bottom-up DP algorithm by reporting, for each step, the cells \(r[j][k]\) and \(s[j][k]\); then write the matrices \(r\) and \(s\).

2. Give the answer to the SSP instance and, if it is yes, reconstruct from the matrix \(s\) a subset of total weight \(c\), as a binary vector \((x_1,x_2,x_3)\).

3. Using the last row of the matrix \(r\), list all the target values \(k\in\{1,2,\dots,7\}\) that are reachable with the 3 items.

Solution

The recurrence and the conventions are those of the box at the beginning of these exercises.

1. Step-by-step execution of the bottom-up DP algorithm. The row \(j=0\) is \(r[0][0]=\mathrm{T}\) and \(r[0][k]=\mathrm{F}\) for \(k\ge 1\), with \(s[0][k]=0\); \(\mathrm{T}\) stands for true and \(\mathrm{F}\) for false. Item \(j\) is used (\(s[j][k]=1\)) only if \(r[j-1][k]\) is \(\mathrm{F}\).

   \(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Action
   \(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]\)	Action
   \(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}\)

   This is the matrix \(r\) after the execution of the DP algorithm:

   \[ \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} \]

   This is the matrix \(s\) after the execution of the DP algorithm:

   \[ \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} \]

2. Since \(r[3][7]=\mathrm{T}\), the answer is yes. Starting from \(j=3\) and \(k=7\):

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

   The vector \((1,0,1)\) selects the subset \(\{1,3\}\), of total weight \(2+5=7=c\). It is the only subset with total weight \(7\).

3. The last row \(r[3][\cdot]\) is \(\mathrm{T}\) exactly for \(k\in\{2,3,5,7\}\): these are the reachable target values. The other values in \(\{1,2,\dots,7\}\) are not the total weight of any subset.

Exercise 20.2: Exercise 2: Subset Sum Problem

Consider the following SSP instance, with target value \(c=9\) and \(3\) items with weights:

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

Questions

1. Show the execution of the bottom-up DP algorithm by reporting, for each step, the cells \(r[j][k]\) and \(s[j][k]\); then write the matrices \(r\) and \(s\).

2. Give the answer to the SSP instance and, if it is yes, reconstruct from the matrix \(s\) a subset of total weight \(c\), as a binary vector \((x_1,x_2,x_3)\).

3. Using the last row of the matrix \(r\), list all the target values \(k\in\{1,2,\dots,9\}\) that are reachable with the 3 items.

Solution

The recurrence and the conventions are those of the box at the beginning of these exercises.

1. Step-by-step execution of the bottom-up DP algorithm. The row \(j=0\) is \(r[0][0]=\mathrm{T}\) and \(r[0][k]=\mathrm{F}\) for \(k\ge 1\), with \(s[0][k]=0\); \(\mathrm{T}\) stands for true and \(\mathrm{F}\) for false. Item \(j\) is used (\(s[j][k]=1\)) only if \(r[j-1][k]\) is \(\mathrm{F}\).

   \(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Action
   \(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]\)	Action
   \(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}\)

   This is the matrix \(r\) after the execution of the DP algorithm:

   \[ \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} \]

   This is the matrix \(s\) after the execution of the DP algorithm:

   \[ \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} \]

2. Since \(r[3][9]=\mathrm{T}\), the answer is yes. Starting from \(j=3\) and \(k=9\):

   Iteration	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	Action
   \(-\)	\(-\)	\(-\)	\(-\)	0	0	0	\(k=9\)
   \(1\)	\(3\)	\(9\)	\(1\)	0	0	1	\(x[3]\leftarrow 1\), \(k\leftarrow 9-6=3\)
   \(2\)	\(2\)	\(3\)	\(0\)	0	0	1	\(x[2]\leftarrow 0\), \(k=3\)
   \(3\)	\(1\)	\(3\)	\(1\)	1	0	1	\(x[1]\leftarrow 1\), \(k\leftarrow 3-3=0\)

   The vector \((1,0,1)\) selects the subset \(\{1,3\}\), of total weight \(3+6=9=c\). It is the only subset with total weight \(9\).

3. The last row \(r[3][\cdot]\) is \(\mathrm{T}\) exactly for \(k\in\{3,4,6,7,9\}\): these are the reachable target values. The other values in \(\{1,2,\dots,9\}\) are not the total weight of any subset.

Exercise 20.3: Exercise 3: Subset Sum Problem

Consider the following SSP instance, with target value \(c=7\) and \(3\) items with weights:

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

Questions

1. Show the execution of the bottom-up DP algorithm by reporting, for each step, the cells \(r[j][k]\) and \(s[j][k]\); then write the matrices \(r\) and \(s\).

2. Give the answer to the SSP instance and, if it is yes, reconstruct from the matrix \(s\) a subset of total weight \(c\), as a binary vector \((x_1,x_2,x_3)\).

3. Using the last row of the matrix \(r\), list all the target values \(k\in\{1,2,\dots,7\}\) that are reachable with the 3 items.

Solution

The recurrence and the conventions are those of the box at the beginning of these exercises.

1. Step-by-step execution of the bottom-up DP algorithm. The row \(j=0\) is \(r[0][0]=\mathrm{T}\) and \(r[0][k]=\mathrm{F}\) for \(k\ge 1\), with \(s[0][k]=0\); \(\mathrm{T}\) stands for true and \(\mathrm{F}\) for false. Item \(j\) is used (\(s[j][k]=1\)) only if \(r[j-1][k]\) is \(\mathrm{F}\).

   \(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Action
   \(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]\)	Action
   \(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}\)

   This is the matrix \(r\) after the execution of the DP algorithm:

   \[ \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} \]

   This is the matrix \(s\) after the execution of the DP algorithm:

   \[ \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} \]

2. Since \(r[3][7]=\mathrm{F}\), the answer is no: no subset of the items has total weight \(7\), and there is nothing to reconstruct. Indeed, all the weights \(w=(2,4,6)\) are even, so every reachable target value is even, while \(c=7\) is odd.

3. The last row \(r[3][\cdot]\) is \(\mathrm{T}\) exactly for \(k\in\{2,4,6\}\): these are the reachable target values. The other values in \(\{1,2,\dots,7\}\) are not the total weight of any subset.

Exercise 20.4: Exercise 4: Subset Sum Problem

Consider the following SSP instance, with target value \(c=8\) and \(4\) items with weights:

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

Questions

1. Show the execution of the bottom-up DP algorithm by reporting, for each step, the cells \(r[j][k]\) and \(s[j][k]\); then write the matrices \(r\) and \(s\).

2. Give the answer to the SSP instance and, if it is yes, reconstruct from the matrix \(s\) a subset of total weight \(c\), as a binary vector \((x_1,x_2,x_3,x_4)\).

3. Using the last row of the matrix \(r\), list all the target values \(k\in\{1,2,\dots,8\}\) that are reachable with the 4 items.

Solution

The recurrence and the conventions are those of the box at the beginning of these exercises.

1. Step-by-step execution of the bottom-up DP algorithm. The row \(j=0\) is \(r[0][0]=\mathrm{T}\) and \(r[0][k]=\mathrm{F}\) for \(k\ge 1\), with \(s[0][k]=0\); \(\mathrm{T}\) stands for true and \(\mathrm{F}\) for false. Item \(j\) is used (\(s[j][k]=1\)) only if \(r[j-1][k]\) is \(\mathrm{F}\).

   \(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Action
   \(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]\)	Action
   \(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}\)

   This is the matrix \(r\) after the execution of the DP algorithm:

   \[ \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} \]

   This is the matrix \(s\) after the execution of the DP algorithm:

   \[ \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} \]

2. Since \(r[4][8]=\mathrm{T}\), the answer is yes. Starting from \(j=4\) and \(k=8\):

   Iteration	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	Action
   \(-\)	\(-\)	\(-\)	\(-\)	0	0	0	0	\(k=8\)
   \(1\)	\(4\)	\(8\)	\(1\)	0	0	0	1	\(x[4]\leftarrow 1\), \(k\leftarrow 8-7=1\)
   \(2\)	\(3\)	\(1\)	\(0\)	0	0	0	1	\(x[3]\leftarrow 0\), \(k=1\)
   \(3\)	\(2\)	\(1\)	\(0\)	0	0	0	1	\(x[2]\leftarrow 0\), \(k=1\)
   \(4\)	\(1\)	\(1\)	\(1\)	1	0	0	1	\(x[1]\leftarrow 1\), \(k\leftarrow 1-1=0\)

   The vector \((1,0,0,1)\) selects the subset \(\{1,4\}\), of total weight \(1+7=8=c\). It is the only subset with total weight \(8\).

3. The last row \(r[4][\cdot]\) is \(\mathrm{T}\) exactly for \(k\in\{1,4,5,6,7,8\}\): these are the reachable target values. The other values in \(\{1,2,\dots,8\}\) are not the total weight of any subset.

Exercise 20.5: Exercise 5: Subset Sum Problem

Consider the following SSP instance, with target value \(c=8\) and \(4\) items with weights:

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

Questions

1. Show the execution of the bottom-up DP algorithm by reporting, for each step, the cells \(r[j][k]\) and \(s[j][k]\); then write the matrices \(r\) and \(s\).

2. Give the answer to the SSP instance and, if it is yes, reconstruct from the matrix \(s\) a subset of total weight \(c\), as a binary vector \((x_1,x_2,x_3,x_4)\).

3. Using the last row of the matrix \(r\), list all the target values \(k\in\{1,2,\dots,8\}\) that are reachable with the 4 items.

Solution

The recurrence and the conventions are those of the box at the beginning of these exercises.

1. Step-by-step execution of the bottom-up DP algorithm. The row \(j=0\) is \(r[0][0]=\mathrm{T}\) and \(r[0][k]=\mathrm{F}\) for \(k\ge 1\), with \(s[0][k]=0\); \(\mathrm{T}\) stands for true and \(\mathrm{F}\) for false. Item \(j\) is used (\(s[j][k]=1\)) only if \(r[j-1][k]\) is \(\mathrm{F}\).

   \(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Action
   \(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]\)	Action
   \(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}\)

   This is the matrix \(r\) after the execution of the DP algorithm:

   \[ \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} \]

   This is the matrix \(s\) after the execution of the DP algorithm:

   \[ \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} \]

2. Since \(r[4][8]=\mathrm{T}\), the answer is yes. Starting from \(j=4\) and \(k=8\):

   Iteration	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	Action
   \(-\)	\(-\)	\(-\)	\(-\)	0	0	0	0	\(k=8\)
   \(1\)	\(4\)	\(8\)	\(0\)	0	0	0	0	\(x[4]\leftarrow 0\), \(k=8\)
   \(2\)	\(3\)	\(8\)	\(1\)	0	0	1	0	\(x[3]\leftarrow 1\), \(k\leftarrow 8-6=2\)
   \(3\)	\(2\)	\(2\)	\(0\)	0	0	1	0	\(x[2]\leftarrow 0\), \(k=2\)
   \(4\)	\(1\)	\(2\)	\(1\)	1	0	1	0	\(x[1]\leftarrow 1\), \(k\leftarrow 2-2=0\)

   The vector \((1,0,1,0)\) selects the subset \(\{1,3\}\), of total weight \(2+6=8=c\). It is the only subset with total weight \(8\).

3. The last row \(r[4][\cdot]\) is \(\mathrm{T}\) exactly for \(k\in\{2,5,6,7,8\}\): these are the reachable target values. The other values in \(\{1,2,\dots,8\}\) are not the total weight of any subset.