Exercises · DP for the unbounded knapsack problem¶

Exercises · Chapter 18 · each solution opens with a click · Chapter 18: Unbounded knapsack (UKP) · Exercises, volume 3 (PDF)

Exercise 18.1: The two DP algorithms for the UKP (4 item types, \(c=7\))

Consider the following UKP instance, where the knapsack has capacity \(c=7\), each item type is available in infinitely many copies, and the profits and weights associated with the item types are:

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

Questions

Show the execution of the first bottom-up DP algorithm by reporting, for each iteration, the values of the vector \(v\) and the values of the vector \(s\).
Using the vector \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,\dots,x_n)\), and report the optimal value.
Show the execution of the second 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,\dots,x_n)\), and report the optimal value.

Solution

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

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

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

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

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

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

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

We have the following vector \(s\):

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

\[ v[7]=14. \]

Step-by-step execution of the second 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. All entries in row \(j=0\) are initialized to \(0\).

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

This is the matrix \(v\) after the execution of the second 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 & 0 & 4 & 4 & 8 & 8 & 12 & 12 \\ {j=2} & 0 & 0 & 4 & 5 & 8 & 9 & 12 & 13 \\ {j=3} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ {j=4} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ \hline \end{array} \]

This is the matrix \(s\) after the execution of the second 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 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

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

Exercise 18.2: The two DP algorithms for the UKP (5 item types, \(c=8\))

Consider the following UKP instance, where the knapsack has capacity \(c=8\), each item type is available in infinitely many copies, and the profits and weights associated with the item types are:

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

Questions

Show the execution of the first bottom-up DP algorithm by reporting, for each iteration, the values of the vector \(v\) and the values of the vector \(s\).
Using the vector \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,\dots,x_n)\), and report the optimal value.
Show the execution of the second 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,\dots,x_n)\), and report the optimal value.

Solution

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

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

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

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

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

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

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

We have the following vector \(s\):

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

\[ v[8]=20. \]

Step-by-step execution of the second 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. All entries in row \(j=0\) are initialized to \(0\).

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

This is the matrix \(v\) after the execution of the second 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 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 \\ {j=2} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ {j=3} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ {j=4} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ {j=5} & 0 & 2 & 5 & 7 & 10 & 12 & 15 & 17 & 20 \\ \hline \end{array} \]

This is the matrix \(s\) after the execution of the second 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

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

Exercise 18.3: The two DP algorithms for the UKP (4 item types, \(c=10\))

Consider the following UKP instance, where the knapsack has capacity \(c=10\), each item type is available in infinitely many copies, and the profits and weights associated with the item types are:

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

Questions

Show the execution of the first bottom-up DP algorithm by reporting, for each iteration, the values of the vector \(v\) and the values of the vector \(s\).
Using the vector \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,\dots,x_n)\), and report the optimal value.
Show the execution of the second 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,\dots,x_n)\), and report the optimal value.

Solution

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

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

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

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

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

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

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

We have the following vector \(s\):

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

We can reconstruct an optimal solution by starting from \(k=10\) as follows:

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

Thus, the vector

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

is an optimal solution. The optimal value is

\[ v[10]=22. \]

Step-by-step execution of the second 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. All entries in row \(j=0\) are initialized to \(0\).

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

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

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

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

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

We have the following matrix \(s\):

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

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

The optimal solution is not unique: \((0,1,1,0)\), with total weight \(4+6=10\) and total profit \(10+12=22\), is also optimal. Both DP algorithms find \((2,1,0,0)\), because they update the stored value only when it strictly improves.

Exercise 18.4: The two DP algorithms for the UKP (4 item types, \(c=9\))

Consider the following UKP instance, where the knapsack has capacity \(c=9\), each item type is available in infinitely many copies, and the profits and weights associated with the item types are:

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

Questions

Show the execution of the first bottom-up DP algorithm by reporting, for each iteration, the values of the vector \(v\) and the values of the vector \(s\).
Using the vector \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,\dots,x_n)\), and report the optimal value.
Show the execution of the second 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,\dots,x_n)\), and report the optimal value.

Solution

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

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

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

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

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

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

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

We have the following vector \(s\):

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

\[ v[9]=23. \]

Step-by-step execution of the second 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. All entries in row \(j=0\) are initialized to \(0\).

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

This is the matrix \(v\) after the execution of the second 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 & 5 & 5 & 10 & 10 & 15 & 15 & 20 & 20 \\ {j=2} & 0 & 0 & 5 & 6 & 10 & 11 & 15 & 16 & 20 & 21 \\ {j=3} & 0 & 0 & 5 & 6 & 10 & 11 & 15 & 16 & 20 & 21 \\ {j=4} & 0 & 0 & 5 & 6 & 10 & 11 & 15 & 18 & 20 & 23 \\ \hline \end{array} \]

This is the matrix \(s\) after the execution of the second 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 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array} \]

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

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

Exercise 18.5: The two DP algorithms for the UKP (5 item types, \(c=11\))

Consider the following UKP instance, where the knapsack has capacity \(c=11\), each item type is available in infinitely many copies, and the profits and weights associated with the item types are:

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

Questions

Show the execution of the first bottom-up DP algorithm by reporting, for each iteration, the values of the vector \(v\) and the values of the vector \(s\).
Using the vector \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,\dots,x_n)\), and report the optimal value.
Show the execution of the second 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,\dots,x_n)\), and report the optimal value.

Solution

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

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

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

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

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

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

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

We have the following vector \(s\):

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

We can reconstruct an optimal solution by starting from \(k=11\) as follows:

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

Thus, the vector

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

is an optimal solution. The optimal value is

\[ v[11]=19. \]

Step-by-step execution of the second 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. All entries in row \(j=0\) are initialized to \(0\).

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

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

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

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

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

We have the following matrix \(s\):

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

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

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

Thus, the vector

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

is an optimal solution. The optimal value is

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

The optimal solution is not unique, and the two DP algorithms find different ones: the first finds \((1,0,0,1,0)\), with total weight \(2+9=11\) and total profit \(3+16=19\); the second finds \((0,1,1,0,0)\), with total weight \(5+6=11\) and total profit \(9+10=19\). These are the only two optimal solutions.