Exercises · DP for the coin change problem¶
Exercises · Chapter 27 · each solution opens with a click · Chapter 27: Coin change (CCP) · Exercises, volume 3 (PDF)
Exercise 27.1: Exercise 1: Coin Change Problem
Consider the following CCP instance, where the amount of change to return is \(c=6\), and the denominations are
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the array \(v\) and the array \(s\).
-
Using the array \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2)\), and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
For each step of the DP algorithm, the table shows the amount of change \(k\), the cells \(v[k]\) and \(s[k]\), and the operation performed; \(s[k]\) is the index \(j\) of the denomination of the coin used. In case of ties the smallest index is kept, because \(m\) is updated only when the value is strictly smaller.
\(k\) \(v[k]\) \(s[k]\) Action 0 0 0 \(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\) 1 1 1 \(\min\{1+v[0]\}=\min\{1\}=1\) 2 2 1 \(\min\{1+v[1]\}=\min\{2\}=2\) 3 3 1 \(\min\{1+v[2]\}=\min\{3\}=3\) 4 1 2 \(\min\{1+v[3],\,1+v[0]\}=\min\{4,1\}=1\) 5 2 1 \(\min\{1+v[4],\,1+v[1]\}=\min\{2,2\}=2\) 6 3 1 \(\min\{1+v[5],\,1+v[2]\}=\min\{3,3\}=3\) This is the array \(v\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {v[k]} & 0 & 1 & 2 & 3 & 1 & 2 & 3 \\ \hline \end{array} \]This is the array \(s\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {s[k]} & 0 & 1 & 1 & 1 & 2 & 1 & 1 \\ \hline \end{array} \] -
We have the following array \(s\):
\[ \begin{array}{l|rrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {s[k]} & 0 & 1 & 1 & 1 & 2 & 1 & 1 \\ \hline \end{array} \]We can reconstruct an optimal solution by starting from \(k=6\) as follows:
Iteration \(k\) \(s[k]\) \(x[1]\) \(x[2]\) \(k \leftarrow k-w_{s[k]}\) \(-\) \(-\) \(-\) 0 0 \(k=6\) \(1\) \(6\) \(1\) 1 0 \(k=6-1=5\) \(2\) \(5\) \(1\) 2 0 \(k=5-1=4\) \(3\) \(4\) \(2\) 2 1 \(k=4-4=0\) Thus, the vector
\[ (2,1) \]is an optimal solution: its total value is \(2\cdot1+1\cdot4=6=c\). The optimal value is
\[ v[6]=3. \]
Exercise 27.2: Exercise 2: Coin Change Problem
Consider the following CCP instance, where the amount of change to return is \(c=11\), and the denominations are
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the array \(v\) and the array \(s\).
-
Using the array \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2)\), and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
For each step of the DP algorithm, the table shows the amount of change \(k\), the cells \(v[k]\) and \(s[k]\), and the operation performed; \(s[k]\) is the index \(j\) of the denomination of the coin used. In case of ties the smallest index is kept, because \(m\) is updated only when the value is strictly smaller. The value \(+\infty\) denotes an amount of change that cannot be returned, for which \(s[k]=0\).
\(k\) \(v[k]\) \(s[k]\) Action 0 0 0 \(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\) 1 \(+\infty\) 0 no denomination \(w_j\le 1\): \(v[1]\leftarrow +\infty\) 2 \(+\infty\) 0 no denomination \(w_j\le 2\): \(v[2]\leftarrow +\infty\) 3 1 1 \(\min\{1+v[0]\}=\min\{1\}=1\) 4 \(+\infty\) 0 \(\min\{1+v[1]\}=\min\{+\infty\}=+\infty\) 5 1 2 \(\min\{1+v[2],\,1+v[0]\}=\min\{+\infty,1\}=1\) 6 2 1 \(\min\{1+v[3],\,1+v[1]\}=\min\{2,+\infty\}=2\) 7 \(+\infty\) 0 \(\min\{1+v[4],\,1+v[2]\}=\min\{+\infty,+\infty\}=+\infty\) 8 2 1 \(\min\{1+v[5],\,1+v[3]\}=\min\{2,2\}=2\) 9 3 1 \(\min\{1+v[6],\,1+v[4]\}=\min\{3,+\infty\}=3\) 10 2 2 \(\min\{1+v[7],\,1+v[5]\}=\min\{+\infty,2\}=2\) 11 3 1 \(\min\{1+v[8],\,1+v[6]\}=\min\{3,3\}=3\) This is the array \(v\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {v[k]} & 0 & {+\infty} & {+\infty} & 1 & {+\infty} & 1 & 2 & {+\infty} & 2 & 3 & 2 & 3 \\ \hline \end{array} \]This is the array \(s\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 1 & 1 & 2 & 1 \\ \hline \end{array} \] -
We have the following array \(s\):
\[ \begin{array}{l|rrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 1 & 1 & 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[2]\) \(k \leftarrow k-w_{s[k]}\) \(-\) \(-\) \(-\) 0 0 \(k=11\) \(1\) \(11\) \(1\) 1 0 \(k=11-3=8\) \(2\) \(8\) \(1\) 2 0 \(k=8-3=5\) \(3\) \(5\) \(2\) 2 1 \(k=5-5=0\) Thus, the vector
\[ (2,1) \]is an optimal solution: its total value is \(2\cdot3+1\cdot5=11=c\). The optimal value is
\[ v[11]=3. \]
Exercise 27.3: Exercise 3: Coin Change Problem
Consider the following CCP instance, where the amount of change to return is \(c=7\), and the denominations are
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the array \(v\) and the array \(s\).
-
Using the array \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2)\), or explain why the instance is infeasible, and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
For each step of the DP algorithm, the table shows the amount of change \(k\), the cells \(v[k]\) and \(s[k]\), and the operation performed; \(s[k]\) is the index \(j\) of the denomination of the coin used. In case of ties the smallest index is kept, because \(m\) is updated only when the value is strictly smaller. The value \(+\infty\) denotes an amount of change that cannot be returned, for which \(s[k]=0\).
\(k\) \(v[k]\) \(s[k]\) Action 0 0 0 \(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\) 1 \(+\infty\) 0 no denomination \(w_j\le 1\): \(v[1]\leftarrow +\infty\) 2 1 1 \(\min\{1+v[0]\}=\min\{1\}=1\) 3 \(+\infty\) 0 \(\min\{1+v[1]\}=\min\{+\infty\}=+\infty\) 4 1 2 \(\min\{1+v[2],\,1+v[0]\}=\min\{2,1\}=1\) 5 \(+\infty\) 0 \(\min\{1+v[3],\,1+v[1]\}=\min\{+\infty,+\infty\}=+\infty\) 6 2 1 \(\min\{1+v[4],\,1+v[2]\}=\min\{2,2\}=2\) 7 \(+\infty\) 0 \(\min\{1+v[5],\,1+v[3]\}=\min\{+\infty,+\infty\}=+\infty\) This is the array \(v\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline {v[k]} & 0 & {+\infty} & 1 & {+\infty} & 1 & {+\infty} & 2 & {+\infty} \\ \hline \end{array} \]This is the array \(s\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline {s[k]} & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 0 \\ \hline \end{array} \] -
Since \(v[7]=+\infty\), the instance is infeasible: no combination of coins of denominations \(w=(2,4)\) returns an amount of change exactly equal to \(c=7\). Indeed, every denomination is even, so every amount of change that can be returned is even, while \(c=7\) is odd.
Since \(s[7]=0\), there is no solution to reconstruct. The optimal value is
\[ v[7]=+\infty. \]
Exercise 27.4: Exercise 4: Coin Change Problem
Consider the following CCP instance, where the amount of change to return is \(c=12\), and the denominations are
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the array \(v\) and the array \(s\).
-
Using the array \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2)\), and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
For each step of the DP algorithm, the table shows the amount of change \(k\), the cells \(v[k]\) and \(s[k]\), and the operation performed; \(s[k]\) is the index \(j\) of the denomination of the coin used. In case of ties the smallest index is kept, because \(m\) is updated only when the value is strictly smaller. The value \(+\infty\) denotes an amount of change that cannot be returned, for which \(s[k]=0\).
\(k\) \(v[k]\) \(s[k]\) Action 0 0 0 \(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\) 1 \(+\infty\) 0 no denomination \(w_j\le 1\): \(v[1]\leftarrow +\infty\) 2 \(+\infty\) 0 no denomination \(w_j\le 2\): \(v[2]\leftarrow +\infty\) 3 1 1 \(\min\{1+v[0]\}=\min\{1\}=1\) 4 \(+\infty\) 0 \(\min\{1+v[1]\}=\min\{+\infty\}=+\infty\) 5 \(+\infty\) 0 \(\min\{1+v[2]\}=\min\{+\infty\}=+\infty\) 6 2 1 \(\min\{1+v[3]\}=\min\{2\}=2\) 7 1 2 \(\min\{1+v[4],\,1+v[0]\}=\min\{+\infty,1\}=1\) 8 \(+\infty\) 0 \(\min\{1+v[5],\,1+v[1]\}=\min\{+\infty,+\infty\}=+\infty\) 9 3 1 \(\min\{1+v[6],\,1+v[2]\}=\min\{3,+\infty\}=3\) 10 2 1 \(\min\{1+v[7],\,1+v[3]\}=\min\{2,2\}=2\) 11 \(+\infty\) 0 \(\min\{1+v[8],\,1+v[4]\}=\min\{+\infty,+\infty\}=+\infty\) 12 4 1 \(\min\{1+v[9],\,1+v[5]\}=\min\{4,+\infty\}=4\) This is the array \(v\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline {v[k]} & 0 & {+\infty} & {+\infty} & 1 & {+\infty} & {+\infty} & 2 & 1 & {+\infty} & 3 & 2 & {+\infty} & 4 \\ \hline \end{array} \]This is the array \(s\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 \\ \hline \end{array} \] -
We have the following array \(s\):
\[ \begin{array}{l|rrrrrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline {s[k]} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 2 & 0 & 1 & 1 & 0 & 1 \\ \hline \end{array} \]We can reconstruct an optimal solution by starting from \(k=12\) as follows:
Iteration \(k\) \(s[k]\) \(x[1]\) \(x[2]\) \(k \leftarrow k-w_{s[k]}\) \(-\) \(-\) \(-\) 0 0 \(k=12\) \(1\) \(12\) \(1\) 1 0 \(k=12-3=9\) \(2\) \(9\) \(1\) 2 0 \(k=9-3=6\) \(3\) \(6\) \(1\) 3 0 \(k=6-3=3\) \(4\) \(3\) \(1\) 4 0 \(k=3-3=0\) Thus, the vector
\[ (4,0) \]is an optimal solution: its total value is \(4\cdot3=12=c\). The optimal value is
\[ v[12]=4. \]
Exercise 27.5: Exercise 5: Coin Change Problem
Consider the following CCP instance, where the amount of change to return is \(c=9\), and the denominations are
Questions
-
Show the execution of the bottom-up DP algorithm by reporting, for each iteration, the values of the array \(v\) and the array \(s\).
-
Using the array \(s\), reconstruct an optimal solution in integer notation \((x_1,x_2,x_3)\), and report the optimal value.
Solution
-
Step-by-step execution of the bottom-up DP algorithm
For each step of the DP algorithm, the table shows the amount of change \(k\), the cells \(v[k]\) and \(s[k]\), and the operation performed; \(s[k]\) is the index \(j\) of the denomination of the coin used. In case of ties the smallest index is kept, because \(m\) is updated only when the value is strictly smaller. The value \(+\infty\) denotes an amount of change that cannot be returned, for which \(s[k]=0\).
\(k\) \(v[k]\) \(s[k]\) Action 0 0 0 \(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\) 1 \(+\infty\) 0 no denomination \(w_j\le 1\): \(v[1]\leftarrow +\infty\) 2 1 1 \(\min\{1+v[0]\}=\min\{1\}=1\) 3 1 2 \(\min\{1+v[1],\,1+v[0]\}=\min\{+\infty,1\}=1\) 4 2 1 \(\min\{1+v[2],\,1+v[1]\}=\min\{2,+\infty\}=2\) 5 2 1 \(\min\{1+v[3],\,1+v[2]\}=\min\{2,2\}=2\) 6 2 2 \(\min\{1+v[4],\,1+v[3]\}=\min\{3,2\}=2\) 7 1 3 \(\min\{1+v[5],\,1+v[4],\,1+v[0]\}=\min\{3,3,1\}=1\) 8 3 1 \(\min\{1+v[6],\,1+v[5],\,1+v[1]\}=\min\{3,3,+\infty\}=3\) 9 2 1 \(\min\{1+v[7],\,1+v[6],\,1+v[2]\}=\min\{2,3,2\}=2\) This is the array \(v\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline {v[k]} & 0 & {+\infty} & 1 & 1 & 2 & 2 & 2 & 1 & 3 & 2 \\ \hline \end{array} \]This is the array \(s\) after the execution of the DP algorithm:
\[ \begin{array}{l|rrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 1 & 2 & 3 & 1 & 1 \\ \hline \end{array} \] -
We have the following array \(s\):
\[ \begin{array}{l|rrrrrrrrrr} \hline {k} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 1 & 2 & 3 & 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[2]\) \(x[3]\) \(k \leftarrow k-w_{s[k]}\) \(-\) \(-\) \(-\) 0 0 0 \(k=9\) \(1\) \(9\) \(1\) 1 0 0 \(k=9-2=7\) \(2\) \(7\) \(3\) 1 0 1 \(k=7-7=0\) Thus, the vector
\[ (1,0,1) \]is an optimal solution: its total value is \(1\cdot2+1\cdot7=9=c\). The optimal value is
\[ v[9]=2. \]