Exercises · DP for the bounded knapsack problem¶

Exercises · Chapter 19 · each solution opens with a click · Chapter 19: Bounded knapsack (BKP) · Exercises, volume 3 (PDF)

Exercise 19.1: Exercise 1: Bounded Knapsack Problem

Consider the following BKP instance, where the knapsack has capacity \(c=6\), and the profits, weights, and bounds associated with the item types are:

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

Questions

Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrices \(v\) and \(s\).
Using the matrix \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2)\), and report the optimal value.

Solution

Step-by-step execution of the bottom-up DP algorithm

For each step of the DP algorithm, the table shows the values of \(j\) and \(k\), the cells \(v[j][k]\) and \(s[j][k]\), and the operation performed.

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

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

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

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

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

We have the following matrix \(s\):

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

We can reconstruct an optimal solution by starting from \(j=2\) and \(k=6\) as follows:

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

Thus, the vector

\[ (1,1) \]

is an optimal solution. The optimal value is

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

Exercise 19.2: Exercise 2: Bounded Knapsack Problem

Consider the following BKP instance, where the knapsack has capacity \(c=7\), and the profits, weights, and bounds associated with the item types are:

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

Questions

Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrices \(v\) and \(s\).
Using the matrix \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2)\), and report the optimal value.

Solution

Step-by-step execution of the bottom-up DP algorithm

For each step of the DP algorithm, the table shows the values of \(j\) and \(k\), the cells \(v[j][k]\) and \(s[j][k]\), and the operation performed.

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

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

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

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 & 1 & 2 & 3 & 3 & 3 & 3 & 3 \\ {j=2} & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline \end{array} \]

We have the following matrix \(s\):

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

We can reconstruct an optimal solution by starting from \(j=2\) and \(k=7\) as follows:

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

Thus, the vector

\[ (3,1) \]

is an optimal solution. The optimal value is

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

Exercise 19.3: Exercise 3: Bounded Knapsack Problem

Consider the following BKP instance, where the knapsack has capacity \(c=5\), and the profits, weights, and bounds associated with the item types are:

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

Questions

Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrices \(v\) and \(s\).
Using the matrix \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,x_3)\), and report the optimal value.

Solution

Step-by-step execution of the bottom-up DP algorithm

For each step of the DP algorithm, the table shows the values of \(j\) and \(k\), the cells \(v[j][k]\) and \(s[j][k]\), and the operation performed.

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

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

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

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

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

We have the following matrix \(s\):

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

We can reconstruct an optimal solution by starting from \(j=3\) and \(k=5\) as follows:

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

Thus, the vector

\[ (0,1,1) \]

is an optimal solution. The optimal value is

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

Exercise 19.4: Exercise 4: Bounded Knapsack Problem

Consider the following BKP instance, where the knapsack has capacity \(c=8\), and the profits, weights, and bounds associated with the item types are:

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

Questions

Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrices \(v\) and \(s\).
Using the matrix \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2)\), and report the optimal value.

Solution

Step-by-step execution of the bottom-up DP algorithm

For each step of the DP algorithm, the table shows the values of \(j\) and \(k\), the cells \(v[j][k]\) and \(s[j][k]\), and the operation performed.

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

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

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

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 & 1 & 2 & 2 & 3 & 3 & 3 \\ {j=2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]

We have the following matrix \(s\):

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

We can reconstruct an optimal solution by starting from \(j=2\) and \(k=8\) as follows:

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

Thus, the vector

\[ (3,0) \]

is an optimal solution. The optimal value is

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

Exercise 19.5: Exercise 5: Bounded Knapsack Problem

Consider the following BKP instance, where the knapsack has capacity \(c=9\), and the profits, weights, and bounds associated with the item types are:

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

Questions

Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the matrices \(v\) and \(s\).
Using the matrix \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,x_3)\), and report the optimal value.

Solution

Step-by-step execution of the bottom-up DP algorithm

For each step of the DP algorithm, the table shows the values of \(j\) and \(k\), the cells \(v[j][k]\) and \(s[j][k]\), and the operation performed.

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

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

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

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 & 1 & 1 & 2 & 2 & 2 & 2 \\ {j=2} & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 2 & 1 & 1 \\ \hline \end{array} \]

We have the following matrix \(s\):

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

We can reconstruct an optimal solution by starting from \(j=3\) and \(k=9\) as follows:

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-1\cdot2=7\)
2	2	7	1	0	1	1	\(x[2]\leftarrow 1\), \(k\leftarrow 7-1\cdot4=3\)
3	1	3	1	1	1	1	\(x[1]\leftarrow 1\), \(k\leftarrow 3-1\cdot3=0\)

Thus, the vector

\[ (1,1,1) \]

is an optimal solution. The optimal value is

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