Exercises · DP for the knapsack problem with setups¶

Exercises · Chapter 23 · each solution opens with a click · Chapter 23: Knapsack with setups (KPS) · Exercises, volume 3 (PDF)

Recurrence used in these exercises

The DP algorithm of the chapter «DP for the knapsack problem with setups». The items are numbered class by class, $\mathscr{J}_h=\{\ell_{h-1}+1,\dots,\ell_h\}$, $t_h=|\mathscr{J}_h|$, and $j=\ell_{h-1}+i$ is the $i$-th item of class $h$:

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

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

The optimal value is $v(q,c)$. The choice tables store $s[h][i][k]=1$ if the $i$-th item of class $h$ is selected, and $o[h][k]=1$ if class $h$ is open. The reconstruction scans the classes from $h=q$ and $k=c$: an open class is scanned as in the KP, and then $k$ decreases by $s_h$.

Exercise 23.1: Exercise 1: Knapsack Problem with Setups

Consider the following KPS instance, with a knapsack of capacity $c=7$ and $4$ items partitioned into $q=2$ classes: $\mathscr{J}_1=\{1,2\}$ with $f_1=2$ and $s_1=1$, $\mathscr{J}_2=\{3,4\}$ with $f_2=2$ and $s_2=1$. The revenues and weights are:

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

Questions

Execute the bottom-up DP algorithm and write the table of all the rows $v[h][\cdot]$ and $u[h][i][\cdot]$, in the order of computation.
Write the choice tables $s$ and $o$, reconstruct an optimal solution $(x_1,x_2,x_3,x_4)$, say which classes are open, and report the optimal value.

Solution

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

For each class $h$ the DP algorithm computes the setup row $u[h][0][\cdot]$, the rows of the items of class $h$, and the row $v[h][\cdot]$. In case of ties the item is not selected and the class stays closed. This is the table after the execution of the DP algorithm:

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

These are the computations of the cells used by the reconstruction, in the order in which it reads them:

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

These are the choice tables computed by the DP algorithm:

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

Starting from $h=2$ and $k=7$:

Iteration	Stage	$k$	Choice	$x[2]$	$x[3]$	$x[4]$	Action
$-$	$-$	$-$	$-$	0	0	0	$k=7$
$1$	$h=2$	$7$	$o[2][7]=1$	0	0	0	class $2$ open
$2$	$j=4$	$7$	$s[2][2][7]=1$	0	0	1	$k\leftarrow 7-1=6$
$3$	$j=3$	$6$	$s[2][1][6]=1$	0	1	1	$k\leftarrow 6-2=4$
$-$	$-$	$4$	$-$	0	1	1	setup: $k\leftarrow 4-s_2=3$
$4$	$h=1$	$3$	$o[1][3]=1$	0	1	1	class $1$ open
$5$	$j=2$	$3$	$s[1][2][3]=1$	1	1	1	$k\leftarrow 3-1=2$
$6$	$j=1$	$2$	$s[1][1][2]=0$	1	1	1	$k=2$
$-$	$-$	$2$	$-$	1	1	1	setup: $k\leftarrow 2-s_1=1$

The vector $(0,1,1,1)$ is an optimal solution: both classes are open, and the items $\{2,3,4\}$ are selected. Its total weight is $1+2+1+s_1+s_2=6\le c$, and the optimal value is $v[2][7]=9+3+8-f_1-f_2=16$.

Exercise 23.2: Exercise 2: Knapsack Problem with Setups

Consider the following KPS instance, with a knapsack of capacity $c=7$ and $4$ items partitioned into $q=2$ classes: $\mathscr{J}_1=\{1,2\}$ with $f_1=4$ and $s_1=2$, $\mathscr{J}_2=\{3,4\}$ with $f_2=4$ and $s_2=1$. The revenues and weights are:

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

Questions

Execute the bottom-up DP algorithm and write the table of all the rows $v[h][\cdot]$ and $u[h][i][\cdot]$, in the order of computation.
Write the choice tables $s$ and $o$, reconstruct an optimal solution $(x_1,x_2,x_3,x_4)$, say which classes are open, and report the optimal value.

Solution

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

For each class $h$ the DP algorithm computes the setup row $u[h][0][\cdot]$, the rows of the items of class $h$, and the row $v[h][\cdot]$. In case of ties the item is not selected and the class stays closed. This is the table after the execution of the DP algorithm:

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

These are the computations of the cells used by the reconstruction, in the order in which it reads them:

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

These are the choice tables computed by the DP algorithm:

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

Starting from $h=2$ and $k=7$:

Iteration	Stage	$k$	Choice	$x[3]$	$x[4]$	Action
$-$	$-$	$-$	$-$	0	0	$k=7$
$1$	$h=2$	$7$	$o[2][7]=1$	0	0	class $2$ open
$2$	$j=4$	$7$	$s[2][2][7]=1$	0	1	$k\leftarrow 7-3=4$
$3$	$j=3$	$4$	$s[2][1][4]=1$	1	1	$k\leftarrow 4-3=1$
$-$	$-$	$1$	$-$	1	1	setup: $k\leftarrow 1-s_2=0$
$4$	$h=1$	$0$	$o[1][0]=0$	1	1	class $1$ closed

The vector $(0,0,1,1)$ is an optimal solution: only class $2$ is open, and the items $\{3,4\}$ are selected. Its total weight is $3+3+s_2=7\le c$, and the optimal value is $v[2][7]=9+2-f_2=7$.

Exercise 23.3: Exercise 3: Knapsack Problem with Setups

Consider the following KPS instance, with a knapsack of capacity $c=8$ and $5$ items partitioned into $q=2$ classes: $\mathscr{J}_1=\{1,2\}$ with $f_1=1$ and $s_1=1$, $\mathscr{J}_2=\{3,4,5\}$ with $f_2=2$ and $s_2=2$. The revenues and weights are:

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

Questions

Execute the bottom-up DP algorithm and write the table of all the rows $v[h][\cdot]$ and $u[h][i][\cdot]$, in the order of computation.
Write the choice tables $s$ and $o$, reconstruct an optimal solution $(x_1,x_2,x_3,x_4,x_5)$, say which classes are open, and report the optimal value.

Solution

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

For each class $h$ the DP algorithm computes the setup row $u[h][0][\cdot]$, the rows of the items of class $h$, and the row $v[h][\cdot]$. In case of ties the item is not selected and the class stays closed. This is the table after the execution of the DP algorithm:

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

These are the computations of the cells used by the reconstruction, in the order in which it reads them:

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

These are the choice tables computed by the DP algorithm:

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

Starting from $h=2$ and $k=8$:

Iteration	Stage	$k$	Choice	$x[2]$	$x[4]$	$x[5]$	Action
$-$	$-$	$-$	$-$	0	0	0	$k=8$
$1$	$h=2$	$8$	$o[2][8]=1$	0	0	0	class $2$ open
$2$	$j=5$	$8$	$s[2][3][8]=1$	0	0	1	$k\leftarrow 8-1=7$
$3$	$j=4$	$7$	$s[2][2][7]=1$	0	1	1	$k\leftarrow 7-3=4$
$4$	$j=3$	$4$	$s[2][1][4]=0$	0	1	1	$k=4$
$-$	$-$	$4$	$-$	0	1	1	setup: $k\leftarrow 4-s_2=2$
$5$	$h=1$	$2$	$o[1][2]=1$	0	1	1	class $1$ open
$6$	$j=2$	$2$	$s[1][2][2]=1$	1	1	1	$k\leftarrow 2-1=1$
$7$	$j=1$	$1$	$s[1][1][1]=0$	1	1	1	$k=1$
$-$	$-$	$1$	$-$	1	1	1	setup: $k\leftarrow 1-s_1=0$

The vector $(0,1,0,1,1)$ is an optimal solution: both classes are open, and the items $\{2,4,5\}$ are selected. Its total weight is $1+3+1+s_1+s_2=8\le c$, and the optimal value is $v[2][8]=9+7+9-f_1-f_2=22$.

Exercise 23.4: Exercise 4: Knapsack Problem with Setups

Consider the following KPS instance, with a knapsack of capacity $c=8$ and $5$ items partitioned into $q=2$ classes: $\mathscr{J}_1=\{1,2,3\}$ with $f_1=2$ and $s_1=1$, $\mathscr{J}_2=\{4,5\}$ with $f_2=1$ and $s_2=1$. The revenues and weights are:

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

Questions

Execute the bottom-up DP algorithm and write the table of all the rows $v[h][\cdot]$ and $u[h][i][\cdot]$, in the order of computation.
Write the choice tables $s$ and $o$, reconstruct an optimal solution $(x_1,x_2,x_3,x_4,x_5)$, say which classes are open, and report the optimal value.

Solution

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

For each class $h$ the DP algorithm computes the setup row $u[h][0][\cdot]$, the rows of the items of class $h$, and the row $v[h][\cdot]$. In case of ties the item is not selected and the class stays closed. This is the table after the execution of the DP algorithm:

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

These are the computations of the cells used by the reconstruction, in the order in which it reads them:

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

These are the choice tables computed by the DP algorithm:

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

Starting from $h=2$ and $k=8$:

Iteration	Stage	$k$	Choice	$x[1]$	$x[2]$	$x[3]$	Action
$-$	$-$	$-$	$-$	0	0	0	$k=8$
$1$	$h=2$	$8$	$o[2][8]=0$	0	0	0	class $2$ closed
$2$	$h=1$	$8$	$o[1][8]=1$	0	0	0	class $1$ open
$3$	$j=3$	$8$	$s[1][3][8]=1$	0	0	1	$k\leftarrow 8-4=4$
$4$	$j=2$	$4$	$s[1][2][4]=1$	0	1	1	$k\leftarrow 4-1=3$
$5$	$j=1$	$3$	$s[1][1][3]=1$	1	1	1	$k\leftarrow 3-1=2$
$-$	$-$	$2$	$-$	1	1	1	setup: $k\leftarrow 2-s_1=1$

The vector $(1,1,1,0,0)$ is an optimal solution: only class $1$ is open, and the items $\{1,2,3\}$ are selected. Its total weight is $1+1+4+s_1=7\le c$, and the optimal value is $v[2][8]=6+9+9-f_1=22$.

Exercise 23.5: Exercise 5: Knapsack Problem with Setups

Consider the following KPS instance, with a knapsack of capacity $c=9$ and $5$ items partitioned into $q=2$ classes: $\mathscr{J}_1=\{1,2\}$ with $f_1=3$ and $s_1=2$, $\mathscr{J}_2=\{3,4,5\}$ with $f_2=2$ and $s_2=2$. The revenues and weights are:

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

Questions

Execute the bottom-up DP algorithm and write the table of all the rows $v[h][\cdot]$ and $u[h][i][\cdot]$, in the order of computation.
Write the choice tables $s$ and $o$, reconstruct an optimal solution $(x_1,x_2,x_3,x_4,x_5)$, say which classes are open, and report the optimal value.

Solution

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

For each class $h$ the DP algorithm computes the setup row $u[h][0][\cdot]$, the rows of the items of class $h$, and the row $v[h][\cdot]$. In case of ties the item is not selected and the class stays closed. This is the table after the execution of the DP algorithm:

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

These are the computations of the cells used by the reconstruction, in the order in which it reads them:

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

These are the choice tables computed by the DP algorithm:

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

Starting from $h=2$ and $k=9$:

Iteration	Stage	$k$	Choice	$x[1]$	$x[2]$	$x[3]$	Action
$-$	$-$	$-$	$-$	0	0	0	$k=9$
$1$	$h=2$	$9$	$o[2][9]=1$	0	0	0	class $2$ open
$2$	$j=5$	$9$	$s[2][3][9]=0$	0	0	0	$k=9$
$3$	$j=4$	$9$	$s[2][2][9]=0$	0	0	0	$k=9$
$4$	$j=3$	$9$	$s[2][1][9]=1$	0	0	1	$k\leftarrow 9-1=8$
$-$	$-$	$8$	$-$	0	0	1	setup: $k\leftarrow 8-s_2=6$
$5$	$h=1$	$6$	$o[1][6]=1$	0	0	1	class $1$ open
$6$	$j=2$	$6$	$s[1][2][6]=1$	0	1	1	$k\leftarrow 6-1=5$
$7$	$j=1$	$5$	$s[1][1][5]=1$	1	1	1	$k\leftarrow 5-3=2$
$-$	$-$	$2$	$-$	1	1	1	setup: $k\leftarrow 2-s_1=0$

The vector $(1,1,1,0,0)$ is an optimal solution: both classes are open, and the items $\{1,2,3\}$ are selected. Its total weight is $3+1+1+s_1+s_2=9\le c$, and the optimal value is $v[2][9]=6+5+8-f_1-f_2=14$.

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

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

Iteration	Stage	\(k\)	Choice	\(x[2]\)	\(x[3]\)	\(x[4]\)	Action
\(-\)	\(-\)	\(-\)	\(-\)	0	0	0	\(k=7\)
\(1\)	\(h=2\)	\(7\)	\(o[2][7]=1\)	0	0	0	class \(2\) open
\(2\)	\(j=4\)	\(7\)	\(s[2][2][7]=1\)	0	0	1	\(k\leftarrow 7-1=6\)
\(3\)	\(j=3\)	\(6\)	\(s[2][1][6]=1\)	0	1	1	\(k\leftarrow 6-2=4\)
\(-\)	\(-\)	\(4\)	\(-\)	0	1	1	setup: \(k\leftarrow 4-s_2=3\)
\(4\)	\(h=1\)	\(3\)	\(o[1][3]=1\)	0	1	1	class \(1\) open
\(5\)	\(j=2\)	\(3\)	\(s[1][2][3]=1\)	1	1	1	\(k\leftarrow 3-1=2\)
\(6\)	\(j=1\)	\(2\)	\(s[1][1][2]=0\)	1	1	1	\(k=2\)
\(-\)	\(-\)	\(2\)	\(-\)	1	1	1	setup: \(k\leftarrow 2-s_1=1\)

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

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