Exercises · DP for the rod cutting problem¶
Exercises · Chapter 28 · each solution opens with a click · Chapter 28: Rod cutting (RCP) · Exercises, volume 3 (PDF)
Exercise 28.1: Exercise 1: Rod Cutting Problem
Consider the following RCP instance, where the rod has length \(n=6\), and the profits associated with the possible piece lengths are:
\[
\begin{array}{l|rrrrrr}
\hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} \\
\hline {p_j} & {2} & {5} & {7} & {8} & {10} & {13} \\
\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 \(\ell\) and \(j\), the cells \(v[\ell]\) and \(s[\ell]\), the current value of \(\mathit{m}\), and the current value of \(\mathit{t}\). The cell of \(\mathit{m}\) is highlighted in red when updated; the cell of \(\mathit{t}\) is highlighted in blue when updated; the cells of \(v[\ell]\) and \(s[\ell]\) are highlighted in blue when assigned.
\(\ell\) \(j\) \(v[\ell]\) \(s[\ell]\) \(\mathit{m}\) \(\mathit{t}\) Action \(-\) \(-\) 0 \(-\) \(-\) \(-\) \(v[0]\leftarrow 0\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 1 1 \(-\) \(-\) 2 1 \(p[1]+v[0]=2+0=2>0\): \(\mathit{m}\leftarrow 2\), \(\mathit{t}\leftarrow 1\) \(-\) 2 1 2 1 \(v[1]\leftarrow \mathit{m}=2\), \(s[1]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 2 1 \(-\) \(-\) 4 1 \(p[1]+v[1]=2+2=4>0\): \(\mathit{m}\leftarrow 4\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 5 2 \(p[2]+v[0]=5+0=5>4\): \(\mathit{m}\leftarrow 5\), \(\mathit{t}\leftarrow 2\) \(-\) 5 2 5 2 \(v[2]\leftarrow \mathit{m}=5\), \(s[2]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 3 1 \(-\) \(-\) 7 1 \(p[1]+v[2]=2+5=7>0\): \(\mathit{m}\leftarrow 7\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 7 1 \(p[2]+v[1]=5+2=7=\mathit{m}\): no update 3 \(-\) \(-\) 7 1 \(p[3]+v[0]=7+0=7=\mathit{m}\): no update \(-\) 7 1 7 1 \(v[3]\leftarrow \mathit{m}=7\), \(s[3]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 4 1 \(-\) \(-\) 9 1 \(p[1]+v[3]=2+7=9>0\): \(\mathit{m}\leftarrow 9\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 10 2 \(p[2]+v[2]=5+5=10>9\): \(\mathit{m}\leftarrow 10\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 10 2 \(p[3]+v[1]=7+2=9<10\): no update 4 \(-\) \(-\) 10 2 \(p[4]+v[0]=8+0=8<10\): no update \(-\) 10 2 10 2 \(v[4]\leftarrow \mathit{m}=10\), \(s[4]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 5 1 \(-\) \(-\) 12 1 \(p[1]+v[4]=2+10=12>0\): \(\mathit{m}\leftarrow 12\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 12 1 \(p[2]+v[3]=5+7=12=\mathit{m}\): no update 3 \(-\) \(-\) 12 1 \(p[3]+v[2]=7+5=12=\mathit{m}\): no update 4 \(-\) \(-\) 12 1 \(p[4]+v[1]=8+2=10<12\): no update 5 \(-\) \(-\) 12 1 \(p[5]+v[0]=10+0=10<12\): no update \(-\) 12 1 12 1 \(v[5]\leftarrow \mathit{m}=12\), \(s[5]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 6 1 \(-\) \(-\) 14 1 \(p[1]+v[5]=2+12=14>0\): \(\mathit{m}\leftarrow 14\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 15 2 \(p[2]+v[4]=5+10=15>14\): \(\mathit{m}\leftarrow 15\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 15 2 \(p[3]+v[3]=7+7=14<15\): no update 4 \(-\) \(-\) 15 2 \(p[4]+v[2]=8+5=13<15\): no update 5 \(-\) \(-\) 15 2 \(p[5]+v[1]=10+2=12<15\): no update 6 \(-\) \(-\) 15 2 \(p[6]+v[0]=13+0=13<15\): no update \(-\) 15 2 15 2 \(v[6]\leftarrow \mathit{m}=15\), \(s[6]\leftarrow \mathit{t}=2\) This is the vector \(v\) after the execution of the DP algorithm:
\[ \begin{array}{cccccccc} \hline & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {v[\ell]} & 0 & 2 & 5 & 7 & 10 & 12 & 15 \\ \hline \end{array} \]This is the vector \(s\) after the execution of the DP algorithm:
\[ \begin{array}{ccccccc} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {s[\ell]} & 1 & 2 & 1 & 2 & 1 & 2 \\ \hline \end{array} \] -
We have the following vector \(s\):
\[ \begin{array}{l|rrrrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {s[\ell]} & 1 & 2 & 1 & 2 & 1 & 2 \\ \hline \end{array} \]We can reconstruct an optimal solution for a rod of length \(n=6\) as follows:
Iteration \(j\) \(s[j]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) \(x[6]\) Update of \(j\) - - - 0 0 0 0 0 0 \(j=6\) 1 6 2 0 1 0 0 0 0 \(j=6-2=4\) 2 4 2 0 2 0 0 0 0 \(j=4-2=2\) 3 2 2 0 3 0 0 0 0 \(j=2-2=0\) Thus, the vector
\[ (0,3,0,0,0,0) \]is an optimal solution. The optimal value is
\[ v[6]=15. \] -
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 \(\ell\), the cells \({v}[j][\ell]\) and \({s}[j][\ell]\), and the operation performed. The cells are computed for increasing values of \(j\) and, for each fixed value of \(j\), for increasing values of \(\ell\).
\(j\) \(\ell\) \({v}[j][\ell]\) \({s}[j][\ell]\) Action \(0\) \(0\) 0 0 \({v}[0][0]\leftarrow 0\), \({s}[0][0]\leftarrow 0\) \(0\) \(1\) \(-\infty\) 0 \({v}[0][1]\leftarrow -\infty\), \({s}[0][1]\leftarrow 0\) \(0\) \(2\) \(-\infty\) 0 \({v}[0][2]\leftarrow -\infty\), \({s}[0][2]\leftarrow 0\) \(0\) \(3\) \(-\infty\) 0 \({v}[0][3]\leftarrow -\infty\), \({s}[0][3]\leftarrow 0\) \(0\) \(4\) \(-\infty\) 0 \({v}[0][4]\leftarrow -\infty\), \({s}[0][4]\leftarrow 0\) \(0\) \(5\) \(-\infty\) 0 \({v}[0][5]\leftarrow -\infty\), \({s}[0][5]\leftarrow 0\) \(0\) \(6\) \(-\infty\) 0 \({v}[0][6]\leftarrow -\infty\), \({s}[0][6]\leftarrow 0\) \(1\) \(0\) 0 0 \(j>\ell\): \({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]=-\infty\): \({v}[1][1]\leftarrow 2\), \({s}[1][1]\leftarrow 1\) \(1\) \(2\) 4 1 \(p[1]+{v}[1][1]=2+2>{v}[0][2]=-\infty\): \({v}[1][2]\leftarrow 4\), \({s}[1][2]\leftarrow 1\) \(1\) \(3\) 6 1 \(p[1]+{v}[1][2]=2+4>{v}[0][3]=-\infty\): \({v}[1][3]\leftarrow 6\), \({s}[1][3]\leftarrow 1\) \(1\) \(4\) 8 1 \(p[1]+{v}[1][3]=2+6>{v}[0][4]=-\infty\): \({v}[1][4]\leftarrow 8\), \({s}[1][4]\leftarrow 1\) \(1\) \(5\) 10 1 \(p[1]+{v}[1][4]=2+8>{v}[0][5]=-\infty\): \({v}[1][5]\leftarrow 10\), \({s}[1][5]\leftarrow 1\) \(1\) \(6\) 12 1 \(p[1]+{v}[1][5]=2+10>{v}[0][6]=-\infty\): \({v}[1][6]\leftarrow 12\), \({s}[1][6]\leftarrow 1\) \(2\) \(0\) 0 0 \(j>\ell\): \({v}[2][0]\leftarrow {v}[1][0]=0\), \({s}[2][0]\leftarrow 0\) \(2\) \(1\) 2 0 \(j>\ell\): \({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\) \(3\) \(0\) 0 0 \(j>\ell\): \({v}[3][0]\leftarrow {v}[2][0]=0\), \({s}[3][0]\leftarrow 0\) \(3\) \(1\) 2 0 \(j>\ell\): \({v}[3][1]\leftarrow {v}[2][1]=2\), \({s}[3][1]\leftarrow 0\) \(3\) \(2\) 5 0 \(j>\ell\): \({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 {v}[2][3]=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 {v}[2][4]=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 {v}[2][5]=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 {v}[2][6]=15\), \({s}[3][6]\leftarrow 0\) \(4\) \(0\) 0 0 \(j>\ell\): \({v}[4][0]\leftarrow {v}[3][0]=0\), \({s}[4][0]\leftarrow 0\) \(4\) \(1\) 2 0 \(j>\ell\): \({v}[4][1]\leftarrow {v}[3][1]=2\), \({s}[4][1]\leftarrow 0\) \(4\) \(2\) 5 0 \(j>\ell\): \({v}[4][2]\leftarrow {v}[3][2]=5\), \({s}[4][2]\leftarrow 0\) \(4\) \(3\) 7 0 \(j>\ell\): \({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 {v}[3][4]=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 {v}[3][5]=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 {v}[3][6]=15\), \({s}[4][6]\leftarrow 0\) \(5\) \(0\) 0 0 \(j>\ell\): \({v}[5][0]\leftarrow {v}[4][0]=0\), \({s}[5][0]\leftarrow 0\) \(5\) \(1\) 2 0 \(j>\ell\): \({v}[5][1]\leftarrow {v}[4][1]=2\), \({s}[5][1]\leftarrow 0\) \(5\) \(2\) 5 0 \(j>\ell\): \({v}[5][2]\leftarrow {v}[4][2]=5\), \({s}[5][2]\leftarrow 0\) \(5\) \(3\) 7 0 \(j>\ell\): \({v}[5][3]\leftarrow {v}[4][3]=7\), \({s}[5][3]\leftarrow 0\) \(5\) \(4\) 10 0 \(j>\ell\): \({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 {v}[4][5]=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 {v}[4][6]=15\), \({s}[5][6]\leftarrow 0\) \(6\) \(0\) 0 0 \(j>\ell\): \({v}[6][0]\leftarrow {v}[5][0]=0\), \({s}[6][0]\leftarrow 0\) \(6\) \(1\) 2 0 \(j>\ell\): \({v}[6][1]\leftarrow {v}[5][1]=2\), \({s}[6][1]\leftarrow 0\) \(6\) \(2\) 5 0 \(j>\ell\): \({v}[6][2]\leftarrow {v}[5][2]=5\), \({s}[6][2]\leftarrow 0\) \(6\) \(3\) 7 0 \(j>\ell\): \({v}[6][3]\leftarrow {v}[5][3]=7\), \({s}[6][3]\leftarrow 0\) \(6\) \(4\) 10 0 \(j>\ell\): \({v}[6][4]\leftarrow {v}[5][4]=10\), \({s}[6][4]\leftarrow 0\) \(6\) \(5\) 12 0 \(j>\ell\): \({v}[6][5]\leftarrow {v}[5][5]=12\), \({s}[6][5]\leftarrow 0\) \(6\) \(6\) 15 0 \(p[6]+{v}[6][0]=13+0\le {v}[5][6]=15\): \({v}[6][6]\leftarrow {v}[5][6]=15\), \({s}[6][6]\leftarrow 0\) These are the matrices \({v}\) and \({s}\) obtained during the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrr} \hline {{v}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {j=0} & 0 & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} \\ {j=1} & 0 & 2 & 4 & 6 & 8 & 10 & 12 \\ {j=2} & 0 & 2 & 5 & 7 & 10 & 12 & 15 \\ {j=3} & 0 & 2 & 5 & 7 & 10 & 12 & 15 \\ {j=4} & 0 & 2 & 5 & 7 & 10 & 12 & 15 \\ {j=5} & 0 & 2 & 5 & 7 & 10 & 12 & 15 \\ {j=6} & 0 & 2 & 5 & 7 & 10 & 12 & 15 \\ \hline \end{array} \]\[ \begin{array}{l|rrrrrrr} \hline {{s}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=6} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]The optimal value of the RCP instance is \({v}[6][6]=15\).
-
Using the matrix \({s}\), we can reconstruct an optimal solution as follows:
Iteration \(j\) \(\ell\) \({s}[j][\ell]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) \(x[6]\) Action 1 6 6 0 0 0 0 0 0 0 \(j\leftarrow 5\) 2 5 6 0 0 0 0 0 0 0 \(j\leftarrow 4\) 3 4 6 0 0 0 0 0 0 0 \(j\leftarrow 3\) 4 3 6 0 0 0 0 0 0 0 \(j\leftarrow 2\) 5 2 6 1 0 1 0 0 0 0 \(\ell\leftarrow 4\) 6 2 4 1 0 2 0 0 0 0 \(\ell\leftarrow 2\) 7 2 2 1 0 3 0 0 0 0 \(\ell\leftarrow 0\) Thus, the vector
\[ (0,3,0,0,0,0) \]is an optimal solution. The optimal value is
\[ {v}[6][6]=15. \]
Exercise 28.2: Exercise 2: Rod Cutting Problem
Consider the following RCP instance, where the rod has length \(n=5\), and the profits associated with the possible piece lengths are:
\[
\begin{array}{l|rrrrr}
\hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\
\hline {p_j} & {1} & {4} & {6} & {8} & {9} \\
\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 \(\ell\) and \(j\), the cells \(v[\ell]\) and \(s[\ell]\), the current value of \(\mathit{m}\), and the current value of \(\mathit{t}\). The cell of \(\mathit{m}\) is highlighted in red when updated; the cell of \(\mathit{t}\) is highlighted in blue when updated; the cells of \(v[\ell]\) and \(s[\ell]\) are highlighted in blue when assigned.
\(\ell\) \(j\) \(v[\ell]\) \(s[\ell]\) \(\mathit{m}\) \(\mathit{t}\) Action \(-\) \(-\) 0 \(-\) \(-\) \(-\) \(v[0]\leftarrow 0\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 1 1 \(-\) \(-\) 1 1 \(p[1]+v[0]=1+0=1>0\): \(\mathit{m}\leftarrow 1\), \(\mathit{t}\leftarrow 1\) \(-\) 1 1 1 1 \(v[1]\leftarrow \mathit{m}=1\), \(s[1]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 2 1 \(-\) \(-\) 2 1 \(p[1]+v[1]=1+1=2>0\): \(\mathit{m}\leftarrow 2\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 4 2 \(p[2]+v[0]=4+0=4>2\): \(\mathit{m}\leftarrow 4\), \(\mathit{t}\leftarrow 2\) \(-\) 4 2 4 2 \(v[2]\leftarrow \mathit{m}=4\), \(s[2]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 3 1 \(-\) \(-\) 5 1 \(p[1]+v[2]=1+4=5>0\): \(\mathit{m}\leftarrow 5\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 5 1 \(p[2]+v[1]=4+1=5=\mathit{m}\): no update 3 \(-\) \(-\) 6 3 \(p[3]+v[0]=6+0=6>5\): \(\mathit{m}\leftarrow 6\), \(\mathit{t}\leftarrow 3\) \(-\) 6 3 6 3 \(v[3]\leftarrow \mathit{m}=6\), \(s[3]\leftarrow \mathit{t}=3\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 4 1 \(-\) \(-\) 7 1 \(p[1]+v[3]=1+6=7>0\): \(\mathit{m}\leftarrow 7\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 8 2 \(p[2]+v[2]=4+4=8>7\): \(\mathit{m}\leftarrow 8\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 8 2 \(p[3]+v[1]=6+1=7<8\): no update 4 \(-\) \(-\) 8 2 \(p[4]+v[0]=8+0=8=\mathit{m}\): no update \(-\) 8 2 8 2 \(v[4]\leftarrow \mathit{m}=8\), \(s[4]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 5 1 \(-\) \(-\) 9 1 \(p[1]+v[4]=1+8=9>0\): \(\mathit{m}\leftarrow 9\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 10 2 \(p[2]+v[3]=4+6=10>9\): \(\mathit{m}\leftarrow 10\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 10 2 \(p[3]+v[2]=6+4=10=\mathit{m}\): no update 4 \(-\) \(-\) 10 2 \(p[4]+v[1]=8+1=9<10\): no update 5 \(-\) \(-\) 10 2 \(p[5]+v[0]=9+0=9<10\): no update \(-\) 10 2 10 2 \(v[5]\leftarrow \mathit{m}=10\), \(s[5]\leftarrow \mathit{t}=2\) This is the vector \(v\) after the execution of the DP algorithm:
\[ \begin{array}{ccccccc} \hline & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {v[\ell]} & 0 & 1 & 4 & 6 & 8 & 10 \\ \hline \end{array} \]This is the vector \(s\) after the execution of the DP algorithm:
\[ \begin{array}{cccccc} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {s[\ell]} & 1 & 2 & 3 & 2 & 2 \\ \hline \end{array} \] -
We have the following vector \(s\):
\[ \begin{array}{l|rrrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {s[\ell]} & 1 & 2 & 3 & 2 & 2 \\ \hline \end{array} \]We can reconstruct an optimal solution for a rod of length \(n=5\) as follows:
Iteration \(j\) \(s[j]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) Update of \(j\) - - - 0 0 0 0 0 \(j=5\) 1 5 2 0 1 0 0 0 \(j=5-2=3\) 2 3 3 0 1 1 0 0 \(j=3-3=0\) Thus, the vector
\[ (0,1,1,0,0) \]is an optimal solution. The optimal value is
\[ v[5]=10. \] -
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 \(\ell\), the cells \({v}[j][\ell]\) and \({s}[j][\ell]\), and the operation performed. The cells are computed for increasing values of \(j\) and, for each fixed value of \(j\), for increasing values of \(\ell\).
\(j\) \(\ell\) \({v}[j][\ell]\) \({s}[j][\ell]\) Action \(0\) \(0\) 0 0 \({v}[0][0]\leftarrow 0\), \({s}[0][0]\leftarrow 0\) \(0\) \(1\) \(-\infty\) 0 \({v}[0][1]\leftarrow -\infty\), \({s}[0][1]\leftarrow 0\) \(0\) \(2\) \(-\infty\) 0 \({v}[0][2]\leftarrow -\infty\), \({s}[0][2]\leftarrow 0\) \(0\) \(3\) \(-\infty\) 0 \({v}[0][3]\leftarrow -\infty\), \({s}[0][3]\leftarrow 0\) \(0\) \(4\) \(-\infty\) 0 \({v}[0][4]\leftarrow -\infty\), \({s}[0][4]\leftarrow 0\) \(0\) \(5\) \(-\infty\) 0 \({v}[0][5]\leftarrow -\infty\), \({s}[0][5]\leftarrow 0\) \(1\) \(0\) 0 0 \(j>\ell\): \({v}[1][0]\leftarrow {v}[0][0]=0\), \({s}[1][0]\leftarrow 0\) \(1\) \(1\) 1 1 \(p[1]+{v}[1][0]=1+0>{v}[0][1]=-\infty\): \({v}[1][1]\leftarrow 1\), \({s}[1][1]\leftarrow 1\) \(1\) \(2\) 2 1 \(p[1]+{v}[1][1]=1+1>{v}[0][2]=-\infty\): \({v}[1][2]\leftarrow 2\), \({s}[1][2]\leftarrow 1\) \(1\) \(3\) 3 1 \(p[1]+{v}[1][2]=1+2>{v}[0][3]=-\infty\): \({v}[1][3]\leftarrow 3\), \({s}[1][3]\leftarrow 1\) \(1\) \(4\) 4 1 \(p[1]+{v}[1][3]=1+3>{v}[0][4]=-\infty\): \({v}[1][4]\leftarrow 4\), \({s}[1][4]\leftarrow 1\) \(1\) \(5\) 5 1 \(p[1]+{v}[1][4]=1+4>{v}[0][5]=-\infty\): \({v}[1][5]\leftarrow 5\), \({s}[1][5]\leftarrow 1\) \(2\) \(0\) 0 0 \(j>\ell\): \({v}[2][0]\leftarrow {v}[1][0]=0\), \({s}[2][0]\leftarrow 0\) \(2\) \(1\) 1 0 \(j>\ell\): \({v}[2][1]\leftarrow {v}[1][1]=1\), \({s}[2][1]\leftarrow 0\) \(2\) \(2\) 4 1 \(p[2]+{v}[2][0]=4+0>{v}[1][2]=2\): \({v}[2][2]\leftarrow 4\), \({s}[2][2]\leftarrow 1\) \(2\) \(3\) 5 1 \(p[2]+{v}[2][1]=4+1>{v}[1][3]=3\): \({v}[2][3]\leftarrow 5\), \({s}[2][3]\leftarrow 1\) \(2\) \(4\) 8 1 \(p[2]+{v}[2][2]=4+4>{v}[1][4]=4\): \({v}[2][4]\leftarrow 8\), \({s}[2][4]\leftarrow 1\) \(2\) \(5\) 9 1 \(p[2]+{v}[2][3]=4+5>{v}[1][5]=5\): \({v}[2][5]\leftarrow 9\), \({s}[2][5]\leftarrow 1\) \(3\) \(0\) 0 0 \(j>\ell\): \({v}[3][0]\leftarrow {v}[2][0]=0\), \({s}[3][0]\leftarrow 0\) \(3\) \(1\) 1 0 \(j>\ell\): \({v}[3][1]\leftarrow {v}[2][1]=1\), \({s}[3][1]\leftarrow 0\) \(3\) \(2\) 4 0 \(j>\ell\): \({v}[3][2]\leftarrow {v}[2][2]=4\), \({s}[3][2]\leftarrow 0\) \(3\) \(3\) 6 1 \(p[3]+{v}[3][0]=6+0>{v}[2][3]=5\): \({v}[3][3]\leftarrow 6\), \({s}[3][3]\leftarrow 1\) \(3\) \(4\) 8 0 \(p[3]+{v}[3][1]=6+1\le {v}[2][4]=8\): \({v}[3][4]\leftarrow {v}[2][4]=8\), \({s}[3][4]\leftarrow 0\) \(3\) \(5\) 10 1 \(p[3]+{v}[3][2]=6+4>{v}[2][5]=9\): \({v}[3][5]\leftarrow 10\), \({s}[3][5]\leftarrow 1\) \(4\) \(0\) 0 0 \(j>\ell\): \({v}[4][0]\leftarrow {v}[3][0]=0\), \({s}[4][0]\leftarrow 0\) \(4\) \(1\) 1 0 \(j>\ell\): \({v}[4][1]\leftarrow {v}[3][1]=1\), \({s}[4][1]\leftarrow 0\) \(4\) \(2\) 4 0 \(j>\ell\): \({v}[4][2]\leftarrow {v}[3][2]=4\), \({s}[4][2]\leftarrow 0\) \(4\) \(3\) 6 0 \(j>\ell\): \({v}[4][3]\leftarrow {v}[3][3]=6\), \({s}[4][3]\leftarrow 0\) \(4\) \(4\) 8 0 \(p[4]+{v}[4][0]=8+0\le {v}[3][4]=8\): \({v}[4][4]\leftarrow {v}[3][4]=8\), \({s}[4][4]\leftarrow 0\) \(4\) \(5\) 10 0 \(p[4]+{v}[4][1]=8+1\le {v}[3][5]=10\): \({v}[4][5]\leftarrow {v}[3][5]=10\), \({s}[4][5]\leftarrow 0\) \(5\) \(0\) 0 0 \(j>\ell\): \({v}[5][0]\leftarrow {v}[4][0]=0\), \({s}[5][0]\leftarrow 0\) \(5\) \(1\) 1 0 \(j>\ell\): \({v}[5][1]\leftarrow {v}[4][1]=1\), \({s}[5][1]\leftarrow 0\) \(5\) \(2\) 4 0 \(j>\ell\): \({v}[5][2]\leftarrow {v}[4][2]=4\), \({s}[5][2]\leftarrow 0\) \(5\) \(3\) 6 0 \(j>\ell\): \({v}[5][3]\leftarrow {v}[4][3]=6\), \({s}[5][3]\leftarrow 0\) \(5\) \(4\) 8 0 \(j>\ell\): \({v}[5][4]\leftarrow {v}[4][4]=8\), \({s}[5][4]\leftarrow 0\) \(5\) \(5\) 10 0 \(p[5]+{v}[5][0]=9+0\le {v}[4][5]=10\): \({v}[5][5]\leftarrow {v}[4][5]=10\), \({s}[5][5]\leftarrow 0\) These are the matrices \({v}\) and \({s}\) obtained during the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrr} \hline {{v}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {j=0} & 0 & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} \\ {j=1} & 0 & 1 & 2 & 3 & 4 & 5 \\ {j=2} & 0 & 1 & 4 & 5 & 8 & 9 \\ {j=3} & 0 & 1 & 4 & 6 & 8 & 10 \\ {j=4} & 0 & 1 & 4 & 6 & 8 & 10 \\ {j=5} & 0 & 1 & 4 & 6 & 8 & 10 \\ \hline \end{array} \]\[ \begin{array}{l|rrrrrr} \hline {{s}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=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 & 1 & 0 & 1 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]The optimal value of the RCP instance is \({v}[5][5]=10\).
-
Using the matrix \({s}\), we can reconstruct an optimal solution as follows:
Iteration \(j\) \(\ell\) \({s}[j][\ell]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) Action 1 5 5 0 0 0 0 0 0 \(j\leftarrow 4\) 2 4 5 0 0 0 0 0 0 \(j\leftarrow 3\) 3 3 5 1 0 0 1 0 0 \(\ell\leftarrow 2\) 4 3 2 0 0 0 1 0 0 \(j\leftarrow 2\) 5 2 2 1 0 1 1 0 0 \(\ell\leftarrow 0\) Thus, the vector
\[ (0,1,1,0,0) \]is an optimal solution. The optimal value is
\[ {v}[5][5]=10. \]
Exercise 28.3: Exercise 3: Rod Cutting Problem
Consider the following RCP instance, where the rod has length \(n=5\), and the profits associated with the possible piece lengths are:
\[
\begin{array}{l|rrrrr}
\hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\
\hline {p_j} & {3} & {5} & {8} & {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 \(\ell\) and \(j\), the cells \(v[\ell]\) and \(s[\ell]\), the current value of \(\mathit{m}\), and the current value of \(\mathit{t}\). The cell of \(\mathit{m}\) is highlighted in red when updated; the cell of \(\mathit{t}\) is highlighted in blue when updated; the cells of \(v[\ell]\) and \(s[\ell]\) are highlighted in blue when assigned.
\(\ell\) \(j\) \(v[\ell]\) \(s[\ell]\) \(\mathit{m}\) \(\mathit{t}\) Action \(-\) \(-\) 0 \(-\) \(-\) \(-\) \(v[0]\leftarrow 0\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 1 1 \(-\) \(-\) 3 1 \(p[1]+v[0]=3+0=3>0\): \(\mathit{m}\leftarrow 3\), \(\mathit{t}\leftarrow 1\) \(-\) 3 1 3 1 \(v[1]\leftarrow \mathit{m}=3\), \(s[1]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 2 1 \(-\) \(-\) 6 1 \(p[1]+v[1]=3+3=6>0\): \(\mathit{m}\leftarrow 6\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 6 1 \(p[2]+v[0]=5+0=5<6\): no update \(-\) 6 1 6 1 \(v[2]\leftarrow \mathit{m}=6\), \(s[2]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 3 1 \(-\) \(-\) 9 1 \(p[1]+v[2]=3+6=9>0\): \(\mathit{m}\leftarrow 9\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 9 1 \(p[2]+v[1]=5+3=8<9\): no update 3 \(-\) \(-\) 9 1 \(p[3]+v[0]=8+0=8<9\): no update \(-\) 9 1 9 1 \(v[3]\leftarrow \mathit{m}=9\), \(s[3]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 4 1 \(-\) \(-\) 12 1 \(p[1]+v[3]=3+9=12>0\): \(\mathit{m}\leftarrow 12\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 12 1 \(p[2]+v[2]=5+6=11<12\): no update 3 \(-\) \(-\) 12 1 \(p[3]+v[1]=8+3=11<12\): no update 4 \(-\) \(-\) 12 1 \(p[4]+v[0]=9+0=9<12\): no update \(-\) 12 1 12 1 \(v[4]\leftarrow \mathit{m}=12\), \(s[4]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 5 1 \(-\) \(-\) 15 1 \(p[1]+v[4]=3+12=15>0\): \(\mathit{m}\leftarrow 15\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 15 1 \(p[2]+v[3]=5+9=14<15\): no update 3 \(-\) \(-\) 15 1 \(p[3]+v[2]=8+6=14<15\): no update 4 \(-\) \(-\) 15 1 \(p[4]+v[1]=9+3=12<15\): no update 5 \(-\) \(-\) 15 1 \(p[5]+v[0]=10+0=10<15\): no update \(-\) 15 1 15 1 \(v[5]\leftarrow \mathit{m}=15\), \(s[5]\leftarrow \mathit{t}=1\) This is the vector \(v\) after the execution of the DP algorithm:
\[ \begin{array}{ccccccc} \hline & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {v[\ell]} & 0 & 3 & 6 & 9 & 12 & 15 \\ \hline \end{array} \]This is the vector \(s\) after the execution of the DP algorithm:
\[ \begin{array}{cccccc} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {s[\ell]} & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \] -
We have the following vector \(s\):
\[ \begin{array}{l|rrrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {s[\ell]} & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \]We can reconstruct an optimal solution for a rod of length \(n=5\) as follows:
Iteration \(j\) \(s[j]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) Update of \(j\) - - - 0 0 0 0 0 \(j=5\) 1 5 1 1 0 0 0 0 \(j=5-1=4\) 2 4 1 2 0 0 0 0 \(j=4-1=3\) 3 3 1 3 0 0 0 0 \(j=3-1=2\) 4 2 1 4 0 0 0 0 \(j=2-1=1\) 5 1 1 5 0 0 0 0 \(j=1-1=0\) Thus, the vector
\[ (5,0,0,0,0) \]is an optimal solution. The optimal value is
\[ v[5]=15. \] -
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 \(\ell\), the cells \({v}[j][\ell]\) and \({s}[j][\ell]\), and the operation performed. The cells are computed for increasing values of \(j\) and, for each fixed value of \(j\), for increasing values of \(\ell\).
\(j\) \(\ell\) \({v}[j][\ell]\) \({s}[j][\ell]\) Action \(0\) \(0\) 0 0 \({v}[0][0]\leftarrow 0\), \({s}[0][0]\leftarrow 0\) \(0\) \(1\) \(-\infty\) 0 \({v}[0][1]\leftarrow -\infty\), \({s}[0][1]\leftarrow 0\) \(0\) \(2\) \(-\infty\) 0 \({v}[0][2]\leftarrow -\infty\), \({s}[0][2]\leftarrow 0\) \(0\) \(3\) \(-\infty\) 0 \({v}[0][3]\leftarrow -\infty\), \({s}[0][3]\leftarrow 0\) \(0\) \(4\) \(-\infty\) 0 \({v}[0][4]\leftarrow -\infty\), \({s}[0][4]\leftarrow 0\) \(0\) \(5\) \(-\infty\) 0 \({v}[0][5]\leftarrow -\infty\), \({s}[0][5]\leftarrow 0\) \(1\) \(0\) 0 0 \(j>\ell\): \({v}[1][0]\leftarrow {v}[0][0]=0\), \({s}[1][0]\leftarrow 0\) \(1\) \(1\) 3 1 \(p[1]+{v}[1][0]=3+0>{v}[0][1]=-\infty\): \({v}[1][1]\leftarrow 3\), \({s}[1][1]\leftarrow 1\) \(1\) \(2\) 6 1 \(p[1]+{v}[1][1]=3+3>{v}[0][2]=-\infty\): \({v}[1][2]\leftarrow 6\), \({s}[1][2]\leftarrow 1\) \(1\) \(3\) 9 1 \(p[1]+{v}[1][2]=3+6>{v}[0][3]=-\infty\): \({v}[1][3]\leftarrow 9\), \({s}[1][3]\leftarrow 1\) \(1\) \(4\) 12 1 \(p[1]+{v}[1][3]=3+9>{v}[0][4]=-\infty\): \({v}[1][4]\leftarrow 12\), \({s}[1][4]\leftarrow 1\) \(1\) \(5\) 15 1 \(p[1]+{v}[1][4]=3+12>{v}[0][5]=-\infty\): \({v}[1][5]\leftarrow 15\), \({s}[1][5]\leftarrow 1\) \(2\) \(0\) 0 0 \(j>\ell\): \({v}[2][0]\leftarrow {v}[1][0]=0\), \({s}[2][0]\leftarrow 0\) \(2\) \(1\) 3 0 \(j>\ell\): \({v}[2][1]\leftarrow {v}[1][1]=3\), \({s}[2][1]\leftarrow 0\) \(2\) \(2\) 6 0 \(p[2]+{v}[2][0]=5+0\le {v}[1][2]=6\): \({v}[2][2]\leftarrow {v}[1][2]=6\), \({s}[2][2]\leftarrow 0\) \(2\) \(3\) 9 0 \(p[2]+{v}[2][1]=5+3\le {v}[1][3]=9\): \({v}[2][3]\leftarrow {v}[1][3]=9\), \({s}[2][3]\leftarrow 0\) \(2\) \(4\) 12 0 \(p[2]+{v}[2][2]=5+6\le {v}[1][4]=12\): \({v}[2][4]\leftarrow {v}[1][4]=12\), \({s}[2][4]\leftarrow 0\) \(2\) \(5\) 15 0 \(p[2]+{v}[2][3]=5+9\le {v}[1][5]=15\): \({v}[2][5]\leftarrow {v}[1][5]=15\), \({s}[2][5]\leftarrow 0\) \(3\) \(0\) 0 0 \(j>\ell\): \({v}[3][0]\leftarrow {v}[2][0]=0\), \({s}[3][0]\leftarrow 0\) \(3\) \(1\) 3 0 \(j>\ell\): \({v}[3][1]\leftarrow {v}[2][1]=3\), \({s}[3][1]\leftarrow 0\) \(3\) \(2\) 6 0 \(j>\ell\): \({v}[3][2]\leftarrow {v}[2][2]=6\), \({s}[3][2]\leftarrow 0\) \(3\) \(3\) 9 0 \(p[3]+{v}[3][0]=8+0\le {v}[2][3]=9\): \({v}[3][3]\leftarrow {v}[2][3]=9\), \({s}[3][3]\leftarrow 0\) \(3\) \(4\) 12 0 \(p[3]+{v}[3][1]=8+3\le {v}[2][4]=12\): \({v}[3][4]\leftarrow {v}[2][4]=12\), \({s}[3][4]\leftarrow 0\) \(3\) \(5\) 15 0 \(p[3]+{v}[3][2]=8+6\le {v}[2][5]=15\): \({v}[3][5]\leftarrow {v}[2][5]=15\), \({s}[3][5]\leftarrow 0\) \(4\) \(0\) 0 0 \(j>\ell\): \({v}[4][0]\leftarrow {v}[3][0]=0\), \({s}[4][0]\leftarrow 0\) \(4\) \(1\) 3 0 \(j>\ell\): \({v}[4][1]\leftarrow {v}[3][1]=3\), \({s}[4][1]\leftarrow 0\) \(4\) \(2\) 6 0 \(j>\ell\): \({v}[4][2]\leftarrow {v}[3][2]=6\), \({s}[4][2]\leftarrow 0\) \(4\) \(3\) 9 0 \(j>\ell\): \({v}[4][3]\leftarrow {v}[3][3]=9\), \({s}[4][3]\leftarrow 0\) \(4\) \(4\) 12 0 \(p[4]+{v}[4][0]=9+0\le {v}[3][4]=12\): \({v}[4][4]\leftarrow {v}[3][4]=12\), \({s}[4][4]\leftarrow 0\) \(4\) \(5\) 15 0 \(p[4]+{v}[4][1]=9+3\le {v}[3][5]=15\): \({v}[4][5]\leftarrow {v}[3][5]=15\), \({s}[4][5]\leftarrow 0\) \(5\) \(0\) 0 0 \(j>\ell\): \({v}[5][0]\leftarrow {v}[4][0]=0\), \({s}[5][0]\leftarrow 0\) \(5\) \(1\) 3 0 \(j>\ell\): \({v}[5][1]\leftarrow {v}[4][1]=3\), \({s}[5][1]\leftarrow 0\) \(5\) \(2\) 6 0 \(j>\ell\): \({v}[5][2]\leftarrow {v}[4][2]=6\), \({s}[5][2]\leftarrow 0\) \(5\) \(3\) 9 0 \(j>\ell\): \({v}[5][3]\leftarrow {v}[4][3]=9\), \({s}[5][3]\leftarrow 0\) \(5\) \(4\) 12 0 \(j>\ell\): \({v}[5][4]\leftarrow {v}[4][4]=12\), \({s}[5][4]\leftarrow 0\) \(5\) \(5\) 15 0 \(p[5]+{v}[5][0]=10+0\le {v}[4][5]=15\): \({v}[5][5]\leftarrow {v}[4][5]=15\), \({s}[5][5]\leftarrow 0\) These are the matrices \({v}\) and \({s}\) obtained during the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrr} \hline {{v}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {j=0} & 0 & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} \\ {j=1} & 0 & 3 & 6 & 9 & 12 & 15 \\ {j=2} & 0 & 3 & 6 & 9 & 12 & 15 \\ {j=3} & 0 & 3 & 6 & 9 & 12 & 15 \\ {j=4} & 0 & 3 & 6 & 9 & 12 & 15 \\ {j=5} & 0 & 3 & 6 & 9 & 12 & 15 \\ \hline \end{array} \]\[ \begin{array}{l|rrrrrr} \hline {{s}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]The optimal value of the RCP instance is \({v}[5][5]=15\).
-
Using the matrix \({s}\), we can reconstruct an optimal solution as follows:
Iteration \(j\) \(\ell\) \({s}[j][\ell]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) Action 1 5 5 0 0 0 0 0 0 \(j\leftarrow 4\) 2 4 5 0 0 0 0 0 0 \(j\leftarrow 3\) 3 3 5 0 0 0 0 0 0 \(j\leftarrow 2\) 4 2 5 0 0 0 0 0 0 \(j\leftarrow 1\) 5 1 5 1 1 0 0 0 0 \(\ell\leftarrow 4\) 6 1 4 1 2 0 0 0 0 \(\ell\leftarrow 3\) 7 1 3 1 3 0 0 0 0 \(\ell\leftarrow 2\) 8 1 2 1 4 0 0 0 0 \(\ell\leftarrow 1\) 9 1 1 1 5 0 0 0 0 \(\ell\leftarrow 0\) Thus, the vector
\[ (5,0,0,0,0) \]is an optimal solution. The optimal value is
\[ {v}[5][5]=15. \]
Exercise 28.4: Exercise 4: Rod Cutting Problem
Consider the following RCP instance, where the rod has length \(n=6\), and the profits associated with the possible piece lengths are:
\[
\begin{array}{l|rrrrrr}
\hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} \\
\hline {p_j} & {2} & {6} & {7} & {11} & {13} & {17} \\
\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 \(\ell\) and \(j\), the cells \(v[\ell]\) and \(s[\ell]\), the current value of \(\mathit{m}\), and the current value of \(\mathit{t}\). The cell of \(\mathit{m}\) is highlighted in red when updated; the cell of \(\mathit{t}\) is highlighted in blue when updated; the cells of \(v[\ell]\) and \(s[\ell]\) are highlighted in blue when assigned.
\(\ell\) \(j\) \(v[\ell]\) \(s[\ell]\) \(\mathit{m}\) \(\mathit{t}\) Action \(-\) \(-\) 0 \(-\) \(-\) \(-\) \(v[0]\leftarrow 0\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 1 1 \(-\) \(-\) 2 1 \(p[1]+v[0]=2+0=2>0\): \(\mathit{m}\leftarrow 2\), \(\mathit{t}\leftarrow 1\) \(-\) 2 1 2 1 \(v[1]\leftarrow \mathit{m}=2\), \(s[1]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 2 1 \(-\) \(-\) 4 1 \(p[1]+v[1]=2+2=4>0\): \(\mathit{m}\leftarrow 4\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 6 2 \(p[2]+v[0]=6+0=6>4\): \(\mathit{m}\leftarrow 6\), \(\mathit{t}\leftarrow 2\) \(-\) 6 2 6 2 \(v[2]\leftarrow \mathit{m}=6\), \(s[2]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 3 1 \(-\) \(-\) 8 1 \(p[1]+v[2]=2+6=8>0\): \(\mathit{m}\leftarrow 8\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 8 1 \(p[2]+v[1]=6+2=8=\mathit{m}\): no update 3 \(-\) \(-\) 8 1 \(p[3]+v[0]=7+0=7<8\): no update \(-\) 8 1 8 1 \(v[3]\leftarrow \mathit{m}=8\), \(s[3]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 4 1 \(-\) \(-\) 10 1 \(p[1]+v[3]=2+8=10>0\): \(\mathit{m}\leftarrow 10\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 12 2 \(p[2]+v[2]=6+6=12>10\): \(\mathit{m}\leftarrow 12\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 12 2 \(p[3]+v[1]=7+2=9<12\): no update 4 \(-\) \(-\) 12 2 \(p[4]+v[0]=11+0=11<12\): no update \(-\) 12 2 12 2 \(v[4]\leftarrow \mathit{m}=12\), \(s[4]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 5 1 \(-\) \(-\) 14 1 \(p[1]+v[4]=2+12=14>0\): \(\mathit{m}\leftarrow 14\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 14 1 \(p[2]+v[3]=6+8=14=\mathit{m}\): no update 3 \(-\) \(-\) 14 1 \(p[3]+v[2]=7+6=13<14\): no update 4 \(-\) \(-\) 14 1 \(p[4]+v[1]=11+2=13<14\): no update 5 \(-\) \(-\) 14 1 \(p[5]+v[0]=13+0=13<14\): no update \(-\) 14 1 14 1 \(v[5]\leftarrow \mathit{m}=14\), \(s[5]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 6 1 \(-\) \(-\) 16 1 \(p[1]+v[5]=2+14=16>0\): \(\mathit{m}\leftarrow 16\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 18 2 \(p[2]+v[4]=6+12=18>16\): \(\mathit{m}\leftarrow 18\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 18 2 \(p[3]+v[3]=7+8=15<18\): no update 4 \(-\) \(-\) 18 2 \(p[4]+v[2]=11+6=17<18\): no update 5 \(-\) \(-\) 18 2 \(p[5]+v[1]=13+2=15<18\): no update 6 \(-\) \(-\) 18 2 \(p[6]+v[0]=17+0=17<18\): no update \(-\) 18 2 18 2 \(v[6]\leftarrow \mathit{m}=18\), \(s[6]\leftarrow \mathit{t}=2\) This is the vector \(v\) after the execution of the DP algorithm:
\[ \begin{array}{cccccccc} \hline & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {v[\ell]} & 0 & 2 & 6 & 8 & 12 & 14 & 18 \\ \hline \end{array} \]This is the vector \(s\) after the execution of the DP algorithm:
\[ \begin{array}{ccccccc} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {s[\ell]} & 1 & 2 & 1 & 2 & 1 & 2 \\ \hline \end{array} \] -
We have the following vector \(s\):
\[ \begin{array}{l|rrrrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {s[\ell]} & 1 & 2 & 1 & 2 & 1 & 2 \\ \hline \end{array} \]We can reconstruct an optimal solution for a rod of length \(n=6\) as follows:
Iteration \(j\) \(s[j]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) \(x[6]\) Update of \(j\) - - - 0 0 0 0 0 0 \(j=6\) 1 6 2 0 1 0 0 0 0 \(j=6-2=4\) 2 4 2 0 2 0 0 0 0 \(j=4-2=2\) 3 2 2 0 3 0 0 0 0 \(j=2-2=0\) Thus, the vector
\[ (0,3,0,0,0,0) \]is an optimal solution. The optimal value is
\[ v[6]=18. \] -
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 \(\ell\), the cells \({v}[j][\ell]\) and \({s}[j][\ell]\), and the operation performed. The cells are computed for increasing values of \(j\) and, for each fixed value of \(j\), for increasing values of \(\ell\).
\(j\) \(\ell\) \({v}[j][\ell]\) \({s}[j][\ell]\) Action \(0\) \(0\) 0 0 \({v}[0][0]\leftarrow 0\), \({s}[0][0]\leftarrow 0\) \(0\) \(1\) \(-\infty\) 0 \({v}[0][1]\leftarrow -\infty\), \({s}[0][1]\leftarrow 0\) \(0\) \(2\) \(-\infty\) 0 \({v}[0][2]\leftarrow -\infty\), \({s}[0][2]\leftarrow 0\) \(0\) \(3\) \(-\infty\) 0 \({v}[0][3]\leftarrow -\infty\), \({s}[0][3]\leftarrow 0\) \(0\) \(4\) \(-\infty\) 0 \({v}[0][4]\leftarrow -\infty\), \({s}[0][4]\leftarrow 0\) \(0\) \(5\) \(-\infty\) 0 \({v}[0][5]\leftarrow -\infty\), \({s}[0][5]\leftarrow 0\) \(0\) \(6\) \(-\infty\) 0 \({v}[0][6]\leftarrow -\infty\), \({s}[0][6]\leftarrow 0\) \(1\) \(0\) 0 0 \(j>\ell\): \({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]=-\infty\): \({v}[1][1]\leftarrow 2\), \({s}[1][1]\leftarrow 1\) \(1\) \(2\) 4 1 \(p[1]+{v}[1][1]=2+2>{v}[0][2]=-\infty\): \({v}[1][2]\leftarrow 4\), \({s}[1][2]\leftarrow 1\) \(1\) \(3\) 6 1 \(p[1]+{v}[1][2]=2+4>{v}[0][3]=-\infty\): \({v}[1][3]\leftarrow 6\), \({s}[1][3]\leftarrow 1\) \(1\) \(4\) 8 1 \(p[1]+{v}[1][3]=2+6>{v}[0][4]=-\infty\): \({v}[1][4]\leftarrow 8\), \({s}[1][4]\leftarrow 1\) \(1\) \(5\) 10 1 \(p[1]+{v}[1][4]=2+8>{v}[0][5]=-\infty\): \({v}[1][5]\leftarrow 10\), \({s}[1][5]\leftarrow 1\) \(1\) \(6\) 12 1 \(p[1]+{v}[1][5]=2+10>{v}[0][6]=-\infty\): \({v}[1][6]\leftarrow 12\), \({s}[1][6]\leftarrow 1\) \(2\) \(0\) 0 0 \(j>\ell\): \({v}[2][0]\leftarrow {v}[1][0]=0\), \({s}[2][0]\leftarrow 0\) \(2\) \(1\) 2 0 \(j>\ell\): \({v}[2][1]\leftarrow {v}[1][1]=2\), \({s}[2][1]\leftarrow 0\) \(2\) \(2\) 6 1 \(p[2]+{v}[2][0]=6+0>{v}[1][2]=4\): \({v}[2][2]\leftarrow 6\), \({s}[2][2]\leftarrow 1\) \(2\) \(3\) 8 1 \(p[2]+{v}[2][1]=6+2>{v}[1][3]=6\): \({v}[2][3]\leftarrow 8\), \({s}[2][3]\leftarrow 1\) \(2\) \(4\) 12 1 \(p[2]+{v}[2][2]=6+6>{v}[1][4]=8\): \({v}[2][4]\leftarrow 12\), \({s}[2][4]\leftarrow 1\) \(2\) \(5\) 14 1 \(p[2]+{v}[2][3]=6+8>{v}[1][5]=10\): \({v}[2][5]\leftarrow 14\), \({s}[2][5]\leftarrow 1\) \(2\) \(6\) 18 1 \(p[2]+{v}[2][4]=6+12>{v}[1][6]=12\): \({v}[2][6]\leftarrow 18\), \({s}[2][6]\leftarrow 1\) \(3\) \(0\) 0 0 \(j>\ell\): \({v}[3][0]\leftarrow {v}[2][0]=0\), \({s}[3][0]\leftarrow 0\) \(3\) \(1\) 2 0 \(j>\ell\): \({v}[3][1]\leftarrow {v}[2][1]=2\), \({s}[3][1]\leftarrow 0\) \(3\) \(2\) 6 0 \(j>\ell\): \({v}[3][2]\leftarrow {v}[2][2]=6\), \({s}[3][2]\leftarrow 0\) \(3\) \(3\) 8 0 \(p[3]+{v}[3][0]=7+0\le {v}[2][3]=8\): \({v}[3][3]\leftarrow {v}[2][3]=8\), \({s}[3][3]\leftarrow 0\) \(3\) \(4\) 12 0 \(p[3]+{v}[3][1]=7+2\le {v}[2][4]=12\): \({v}[3][4]\leftarrow {v}[2][4]=12\), \({s}[3][4]\leftarrow 0\) \(3\) \(5\) 14 0 \(p[3]+{v}[3][2]=7+6\le {v}[2][5]=14\): \({v}[3][5]\leftarrow {v}[2][5]=14\), \({s}[3][5]\leftarrow 0\) \(3\) \(6\) 18 0 \(p[3]+{v}[3][3]=7+8\le {v}[2][6]=18\): \({v}[3][6]\leftarrow {v}[2][6]=18\), \({s}[3][6]\leftarrow 0\) \(4\) \(0\) 0 0 \(j>\ell\): \({v}[4][0]\leftarrow {v}[3][0]=0\), \({s}[4][0]\leftarrow 0\) \(4\) \(1\) 2 0 \(j>\ell\): \({v}[4][1]\leftarrow {v}[3][1]=2\), \({s}[4][1]\leftarrow 0\) \(4\) \(2\) 6 0 \(j>\ell\): \({v}[4][2]\leftarrow {v}[3][2]=6\), \({s}[4][2]\leftarrow 0\) \(4\) \(3\) 8 0 \(j>\ell\): \({v}[4][3]\leftarrow {v}[3][3]=8\), \({s}[4][3]\leftarrow 0\) \(4\) \(4\) 12 0 \(p[4]+{v}[4][0]=11+0\le {v}[3][4]=12\): \({v}[4][4]\leftarrow {v}[3][4]=12\), \({s}[4][4]\leftarrow 0\) \(4\) \(5\) 14 0 \(p[4]+{v}[4][1]=11+2\le {v}[3][5]=14\): \({v}[4][5]\leftarrow {v}[3][5]=14\), \({s}[4][5]\leftarrow 0\) \(4\) \(6\) 18 0 \(p[4]+{v}[4][2]=11+6\le {v}[3][6]=18\): \({v}[4][6]\leftarrow {v}[3][6]=18\), \({s}[4][6]\leftarrow 0\) \(5\) \(0\) 0 0 \(j>\ell\): \({v}[5][0]\leftarrow {v}[4][0]=0\), \({s}[5][0]\leftarrow 0\) \(5\) \(1\) 2 0 \(j>\ell\): \({v}[5][1]\leftarrow {v}[4][1]=2\), \({s}[5][1]\leftarrow 0\) \(5\) \(2\) 6 0 \(j>\ell\): \({v}[5][2]\leftarrow {v}[4][2]=6\), \({s}[5][2]\leftarrow 0\) \(5\) \(3\) 8 0 \(j>\ell\): \({v}[5][3]\leftarrow {v}[4][3]=8\), \({s}[5][3]\leftarrow 0\) \(5\) \(4\) 12 0 \(j>\ell\): \({v}[5][4]\leftarrow {v}[4][4]=12\), \({s}[5][4]\leftarrow 0\) \(5\) \(5\) 14 0 \(p[5]+{v}[5][0]=13+0\le {v}[4][5]=14\): \({v}[5][5]\leftarrow {v}[4][5]=14\), \({s}[5][5]\leftarrow 0\) \(5\) \(6\) 18 0 \(p[5]+{v}[5][1]=13+2\le {v}[4][6]=18\): \({v}[5][6]\leftarrow {v}[4][6]=18\), \({s}[5][6]\leftarrow 0\) \(6\) \(0\) 0 0 \(j>\ell\): \({v}[6][0]\leftarrow {v}[5][0]=0\), \({s}[6][0]\leftarrow 0\) \(6\) \(1\) 2 0 \(j>\ell\): \({v}[6][1]\leftarrow {v}[5][1]=2\), \({s}[6][1]\leftarrow 0\) \(6\) \(2\) 6 0 \(j>\ell\): \({v}[6][2]\leftarrow {v}[5][2]=6\), \({s}[6][2]\leftarrow 0\) \(6\) \(3\) 8 0 \(j>\ell\): \({v}[6][3]\leftarrow {v}[5][3]=8\), \({s}[6][3]\leftarrow 0\) \(6\) \(4\) 12 0 \(j>\ell\): \({v}[6][4]\leftarrow {v}[5][4]=12\), \({s}[6][4]\leftarrow 0\) \(6\) \(5\) 14 0 \(j>\ell\): \({v}[6][5]\leftarrow {v}[5][5]=14\), \({s}[6][5]\leftarrow 0\) \(6\) \(6\) 18 0 \(p[6]+{v}[6][0]=17+0\le {v}[5][6]=18\): \({v}[6][6]\leftarrow {v}[5][6]=18\), \({s}[6][6]\leftarrow 0\) These are the matrices \({v}\) and \({s}\) obtained during the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrr} \hline {{v}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {j=0} & 0 & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} \\ {j=1} & 0 & 2 & 4 & 6 & 8 & 10 & 12 \\ {j=2} & 0 & 2 & 6 & 8 & 12 & 14 & 18 \\ {j=3} & 0 & 2 & 6 & 8 & 12 & 14 & 18 \\ {j=4} & 0 & 2 & 6 & 8 & 12 & 14 & 18 \\ {j=5} & 0 & 2 & 6 & 8 & 12 & 14 & 18 \\ {j=6} & 0 & 2 & 6 & 8 & 12 & 14 & 18 \\ \hline \end{array} \]\[ \begin{array}{l|rrrrrrr} \hline {{s}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=6} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]The optimal value of the RCP instance is \({v}[6][6]=18\).
-
Using the matrix \({s}\), we can reconstruct an optimal solution as follows:
Iteration \(j\) \(\ell\) \({s}[j][\ell]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) \(x[6]\) Action 1 6 6 0 0 0 0 0 0 0 \(j\leftarrow 5\) 2 5 6 0 0 0 0 0 0 0 \(j\leftarrow 4\) 3 4 6 0 0 0 0 0 0 0 \(j\leftarrow 3\) 4 3 6 0 0 0 0 0 0 0 \(j\leftarrow 2\) 5 2 6 1 0 1 0 0 0 0 \(\ell\leftarrow 4\) 6 2 4 1 0 2 0 0 0 0 \(\ell\leftarrow 2\) 7 2 2 1 0 3 0 0 0 0 \(\ell\leftarrow 0\) Thus, the vector
\[ (0,3,0,0,0,0) \]is an optimal solution. The optimal value is
\[ {v}[6][6]=18. \]
Exercise 28.5: Exercise 5: Rod Cutting Problem
Consider the following RCP instance, where the rod has length \(n=6\), and the profits associated with the possible piece lengths are:
\[
\begin{array}{l|rrrrrr}
\hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} \\
\hline {p_j} & {1} & {5} & {8} & {9} & {12} & {14} \\
\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 \(\ell\) and \(j\), the cells \(v[\ell]\) and \(s[\ell]\), the current value of \(\mathit{m}\), and the current value of \(\mathit{t}\). The cell of \(\mathit{m}\) is highlighted in red when updated; the cell of \(\mathit{t}\) is highlighted in blue when updated; the cells of \(v[\ell]\) and \(s[\ell]\) are highlighted in blue when assigned.
\(\ell\) \(j\) \(v[\ell]\) \(s[\ell]\) \(\mathit{m}\) \(\mathit{t}\) Action \(-\) \(-\) 0 \(-\) \(-\) \(-\) \(v[0]\leftarrow 0\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 1 1 \(-\) \(-\) 1 1 \(p[1]+v[0]=1+0=1>0\): \(\mathit{m}\leftarrow 1\), \(\mathit{t}\leftarrow 1\) \(-\) 1 1 1 1 \(v[1]\leftarrow \mathit{m}=1\), \(s[1]\leftarrow \mathit{t}=1\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 2 1 \(-\) \(-\) 2 1 \(p[1]+v[1]=1+1=2>0\): \(\mathit{m}\leftarrow 2\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 5 2 \(p[2]+v[0]=5+0=5>2\): \(\mathit{m}\leftarrow 5\), \(\mathit{t}\leftarrow 2\) \(-\) 5 2 5 2 \(v[2]\leftarrow \mathit{m}=5\), \(s[2]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 3 1 \(-\) \(-\) 6 1 \(p[1]+v[2]=1+5=6>0\): \(\mathit{m}\leftarrow 6\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 6 1 \(p[2]+v[1]=5+1=6=\mathit{m}\): no update 3 \(-\) \(-\) 8 3 \(p[3]+v[0]=8+0=8>6\): \(\mathit{m}\leftarrow 8\), \(\mathit{t}\leftarrow 3\) \(-\) 8 3 8 3 \(v[3]\leftarrow \mathit{m}=8\), \(s[3]\leftarrow \mathit{t}=3\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 4 1 \(-\) \(-\) 9 1 \(p[1]+v[3]=1+8=9>0\): \(\mathit{m}\leftarrow 9\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 10 2 \(p[2]+v[2]=5+5=10>9\): \(\mathit{m}\leftarrow 10\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 10 2 \(p[3]+v[1]=8+1=9<10\): no update 4 \(-\) \(-\) 10 2 \(p[4]+v[0]=9+0=9<10\): no update \(-\) 10 2 10 2 \(v[4]\leftarrow \mathit{m}=10\), \(s[4]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 5 1 \(-\) \(-\) 11 1 \(p[1]+v[4]=1+10=11>0\): \(\mathit{m}\leftarrow 11\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 13 2 \(p[2]+v[3]=5+8=13>11\): \(\mathit{m}\leftarrow 13\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 13 2 \(p[3]+v[2]=8+5=13=\mathit{m}\): no update 4 \(-\) \(-\) 13 2 \(p[4]+v[1]=9+1=10<13\): no update 5 \(-\) \(-\) 13 2 \(p[5]+v[0]=12+0=12<13\): no update \(-\) 13 2 13 2 \(v[5]\leftarrow \mathit{m}=13\), \(s[5]\leftarrow \mathit{t}=2\) \(-\) \(-\) \(-\) 0 0 \(\mathit{m}\leftarrow 0\), \(\mathit{t}\leftarrow 0\) 6 1 \(-\) \(-\) 14 1 \(p[1]+v[5]=1+13=14>0\): \(\mathit{m}\leftarrow 14\), \(\mathit{t}\leftarrow 1\) 2 \(-\) \(-\) 15 2 \(p[2]+v[4]=5+10=15>14\): \(\mathit{m}\leftarrow 15\), \(\mathit{t}\leftarrow 2\) 3 \(-\) \(-\) 16 3 \(p[3]+v[3]=8+8=16>15\): \(\mathit{m}\leftarrow 16\), \(\mathit{t}\leftarrow 3\) 4 \(-\) \(-\) 16 3 \(p[4]+v[2]=9+5=14<16\): no update 5 \(-\) \(-\) 16 3 \(p[5]+v[1]=12+1=13<16\): no update 6 \(-\) \(-\) 16 3 \(p[6]+v[0]=14+0=14<16\): no update \(-\) 16 3 16 3 \(v[6]\leftarrow \mathit{m}=16\), \(s[6]\leftarrow \mathit{t}=3\) This is the vector \(v\) after the execution of the DP algorithm:
\[ \begin{array}{cccccccc} \hline & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {v[\ell]} & 0 & 1 & 5 & 8 & 10 & 13 & 16 \\ \hline \end{array} \]This is the vector \(s\) after the execution of the DP algorithm:
\[ \begin{array}{ccccccc} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {s[\ell]} & 1 & 2 & 3 & 2 & 2 & 3 \\ \hline \end{array} \] -
We have the following vector \(s\):
\[ \begin{array}{l|rrrrrr} \hline & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {s[\ell]} & 1 & 2 & 3 & 2 & 2 & 3 \\ \hline \end{array} \]We can reconstruct an optimal solution for a rod of length \(n=6\) as follows:
Iteration \(j\) \(s[j]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) \(x[6]\) Update of \(j\) - - - 0 0 0 0 0 0 \(j=6\) 1 6 3 0 0 1 0 0 0 \(j=6-3=3\) 2 3 3 0 0 2 0 0 0 \(j=3-3=0\) Thus, the vector
\[ (0,0,2,0,0,0) \]is an optimal solution. The optimal value is
\[ v[6]=16. \] -
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 \(\ell\), the cells \({v}[j][\ell]\) and \({s}[j][\ell]\), and the operation performed. The cells are computed for increasing values of \(j\) and, for each fixed value of \(j\), for increasing values of \(\ell\).
\(j\) \(\ell\) \({v}[j][\ell]\) \({s}[j][\ell]\) Action \(0\) \(0\) 0 0 \({v}[0][0]\leftarrow 0\), \({s}[0][0]\leftarrow 0\) \(0\) \(1\) \(-\infty\) 0 \({v}[0][1]\leftarrow -\infty\), \({s}[0][1]\leftarrow 0\) \(0\) \(2\) \(-\infty\) 0 \({v}[0][2]\leftarrow -\infty\), \({s}[0][2]\leftarrow 0\) \(0\) \(3\) \(-\infty\) 0 \({v}[0][3]\leftarrow -\infty\), \({s}[0][3]\leftarrow 0\) \(0\) \(4\) \(-\infty\) 0 \({v}[0][4]\leftarrow -\infty\), \({s}[0][4]\leftarrow 0\) \(0\) \(5\) \(-\infty\) 0 \({v}[0][5]\leftarrow -\infty\), \({s}[0][5]\leftarrow 0\) \(0\) \(6\) \(-\infty\) 0 \({v}[0][6]\leftarrow -\infty\), \({s}[0][6]\leftarrow 0\) \(1\) \(0\) 0 0 \(j>\ell\): \({v}[1][0]\leftarrow {v}[0][0]=0\), \({s}[1][0]\leftarrow 0\) \(1\) \(1\) 1 1 \(p[1]+{v}[1][0]=1+0>{v}[0][1]=-\infty\): \({v}[1][1]\leftarrow 1\), \({s}[1][1]\leftarrow 1\) \(1\) \(2\) 2 1 \(p[1]+{v}[1][1]=1+1>{v}[0][2]=-\infty\): \({v}[1][2]\leftarrow 2\), \({s}[1][2]\leftarrow 1\) \(1\) \(3\) 3 1 \(p[1]+{v}[1][2]=1+2>{v}[0][3]=-\infty\): \({v}[1][3]\leftarrow 3\), \({s}[1][3]\leftarrow 1\) \(1\) \(4\) 4 1 \(p[1]+{v}[1][3]=1+3>{v}[0][4]=-\infty\): \({v}[1][4]\leftarrow 4\), \({s}[1][4]\leftarrow 1\) \(1\) \(5\) 5 1 \(p[1]+{v}[1][4]=1+4>{v}[0][5]=-\infty\): \({v}[1][5]\leftarrow 5\), \({s}[1][5]\leftarrow 1\) \(1\) \(6\) 6 1 \(p[1]+{v}[1][5]=1+5>{v}[0][6]=-\infty\): \({v}[1][6]\leftarrow 6\), \({s}[1][6]\leftarrow 1\) \(2\) \(0\) 0 0 \(j>\ell\): \({v}[2][0]\leftarrow {v}[1][0]=0\), \({s}[2][0]\leftarrow 0\) \(2\) \(1\) 1 0 \(j>\ell\): \({v}[2][1]\leftarrow {v}[1][1]=1\), \({s}[2][1]\leftarrow 0\) \(2\) \(2\) 5 1 \(p[2]+{v}[2][0]=5+0>{v}[1][2]=2\): \({v}[2][2]\leftarrow 5\), \({s}[2][2]\leftarrow 1\) \(2\) \(3\) 6 1 \(p[2]+{v}[2][1]=5+1>{v}[1][3]=3\): \({v}[2][3]\leftarrow 6\), \({s}[2][3]\leftarrow 1\) \(2\) \(4\) 10 1 \(p[2]+{v}[2][2]=5+5>{v}[1][4]=4\): \({v}[2][4]\leftarrow 10\), \({s}[2][4]\leftarrow 1\) \(2\) \(5\) 11 1 \(p[2]+{v}[2][3]=5+6>{v}[1][5]=5\): \({v}[2][5]\leftarrow 11\), \({s}[2][5]\leftarrow 1\) \(2\) \(6\) 15 1 \(p[2]+{v}[2][4]=5+10>{v}[1][6]=6\): \({v}[2][6]\leftarrow 15\), \({s}[2][6]\leftarrow 1\) \(3\) \(0\) 0 0 \(j>\ell\): \({v}[3][0]\leftarrow {v}[2][0]=0\), \({s}[3][0]\leftarrow 0\) \(3\) \(1\) 1 0 \(j>\ell\): \({v}[3][1]\leftarrow {v}[2][1]=1\), \({s}[3][1]\leftarrow 0\) \(3\) \(2\) 5 0 \(j>\ell\): \({v}[3][2]\leftarrow {v}[2][2]=5\), \({s}[3][2]\leftarrow 0\) \(3\) \(3\) 8 1 \(p[3]+{v}[3][0]=8+0>{v}[2][3]=6\): \({v}[3][3]\leftarrow 8\), \({s}[3][3]\leftarrow 1\) \(3\) \(4\) 10 0 \(p[3]+{v}[3][1]=8+1\le {v}[2][4]=10\): \({v}[3][4]\leftarrow {v}[2][4]=10\), \({s}[3][4]\leftarrow 0\) \(3\) \(5\) 13 1 \(p[3]+{v}[3][2]=8+5>{v}[2][5]=11\): \({v}[3][5]\leftarrow 13\), \({s}[3][5]\leftarrow 1\) \(3\) \(6\) 16 1 \(p[3]+{v}[3][3]=8+8>{v}[2][6]=15\): \({v}[3][6]\leftarrow 16\), \({s}[3][6]\leftarrow 1\) \(4\) \(0\) 0 0 \(j>\ell\): \({v}[4][0]\leftarrow {v}[3][0]=0\), \({s}[4][0]\leftarrow 0\) \(4\) \(1\) 1 0 \(j>\ell\): \({v}[4][1]\leftarrow {v}[3][1]=1\), \({s}[4][1]\leftarrow 0\) \(4\) \(2\) 5 0 \(j>\ell\): \({v}[4][2]\leftarrow {v}[3][2]=5\), \({s}[4][2]\leftarrow 0\) \(4\) \(3\) 8 0 \(j>\ell\): \({v}[4][3]\leftarrow {v}[3][3]=8\), \({s}[4][3]\leftarrow 0\) \(4\) \(4\) 10 0 \(p[4]+{v}[4][0]=9+0\le {v}[3][4]=10\): \({v}[4][4]\leftarrow {v}[3][4]=10\), \({s}[4][4]\leftarrow 0\) \(4\) \(5\) 13 0 \(p[4]+{v}[4][1]=9+1\le {v}[3][5]=13\): \({v}[4][5]\leftarrow {v}[3][5]=13\), \({s}[4][5]\leftarrow 0\) \(4\) \(6\) 16 0 \(p[4]+{v}[4][2]=9+5\le {v}[3][6]=16\): \({v}[4][6]\leftarrow {v}[3][6]=16\), \({s}[4][6]\leftarrow 0\) \(5\) \(0\) 0 0 \(j>\ell\): \({v}[5][0]\leftarrow {v}[4][0]=0\), \({s}[5][0]\leftarrow 0\) \(5\) \(1\) 1 0 \(j>\ell\): \({v}[5][1]\leftarrow {v}[4][1]=1\), \({s}[5][1]\leftarrow 0\) \(5\) \(2\) 5 0 \(j>\ell\): \({v}[5][2]\leftarrow {v}[4][2]=5\), \({s}[5][2]\leftarrow 0\) \(5\) \(3\) 8 0 \(j>\ell\): \({v}[5][3]\leftarrow {v}[4][3]=8\), \({s}[5][3]\leftarrow 0\) \(5\) \(4\) 10 0 \(j>\ell\): \({v}[5][4]\leftarrow {v}[4][4]=10\), \({s}[5][4]\leftarrow 0\) \(5\) \(5\) 13 0 \(p[5]+{v}[5][0]=12+0\le {v}[4][5]=13\): \({v}[5][5]\leftarrow {v}[4][5]=13\), \({s}[5][5]\leftarrow 0\) \(5\) \(6\) 16 0 \(p[5]+{v}[5][1]=12+1\le {v}[4][6]=16\): \({v}[5][6]\leftarrow {v}[4][6]=16\), \({s}[5][6]\leftarrow 0\) \(6\) \(0\) 0 0 \(j>\ell\): \({v}[6][0]\leftarrow {v}[5][0]=0\), \({s}[6][0]\leftarrow 0\) \(6\) \(1\) 1 0 \(j>\ell\): \({v}[6][1]\leftarrow {v}[5][1]=1\), \({s}[6][1]\leftarrow 0\) \(6\) \(2\) 5 0 \(j>\ell\): \({v}[6][2]\leftarrow {v}[5][2]=5\), \({s}[6][2]\leftarrow 0\) \(6\) \(3\) 8 0 \(j>\ell\): \({v}[6][3]\leftarrow {v}[5][3]=8\), \({s}[6][3]\leftarrow 0\) \(6\) \(4\) 10 0 \(j>\ell\): \({v}[6][4]\leftarrow {v}[5][4]=10\), \({s}[6][4]\leftarrow 0\) \(6\) \(5\) 13 0 \(j>\ell\): \({v}[6][5]\leftarrow {v}[5][5]=13\), \({s}[6][5]\leftarrow 0\) \(6\) \(6\) 16 0 \(p[6]+{v}[6][0]=14+0\le {v}[5][6]=16\): \({v}[6][6]\leftarrow {v}[5][6]=16\), \({s}[6][6]\leftarrow 0\) These are the matrices \({v}\) and \({s}\) obtained during the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrr} \hline {{v}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {j=0} & 0 & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {-\infty} \\ {j=1} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ {j=2} & 0 & 1 & 5 & 6 & 10 & 11 & 15 \\ {j=3} & 0 & 1 & 5 & 8 & 10 & 13 & 16 \\ {j=4} & 0 & 1 & 5 & 8 & 10 & 13 & 16 \\ {j=5} & 0 & 1 & 5 & 8 & 10 & 13 & 16 \\ {j=6} & 0 & 1 & 5 & 8 & 10 & 13 & 16 \\ \hline \end{array} \]\[ \begin{array}{l|rrrrrrr} \hline {{s}[j][\ell]} & {\ell=0} & {\ell=1} & {\ell=2} & {\ell=3} & {\ell=4} & {\ell=5} & {\ell=6} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ {j=3} & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=6} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]The optimal value of the RCP instance is \({v}[6][6]=16\).
-
Using the matrix \({s}\), we can reconstruct an optimal solution as follows:
Iteration \(j\) \(\ell\) \({s}[j][\ell]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(x[5]\) \(x[6]\) Action 1 6 6 0 0 0 0 0 0 0 \(j\leftarrow 5\) 2 5 6 0 0 0 0 0 0 0 \(j\leftarrow 4\) 3 4 6 0 0 0 0 0 0 0 \(j\leftarrow 3\) 4 3 6 1 0 0 1 0 0 0 \(\ell\leftarrow 3\) 5 3 3 1 0 0 2 0 0 0 \(\ell\leftarrow 0\) Thus, the vector
\[ (0,0,2,0,0,0) \]is an optimal solution. The optimal value is
\[ {v}[6][6]=16. \]