Question

Consider the following variation on the change-making problem (Exercise 6.17): you are given denominations ${\mathit{x}}_{\mathbf{1}}\mathbf{,}{\mathit{x}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{,}{\mathit{x}}_{\mathbf{n}}$, and you want to make change for a value $\mathbf{v}$, but you are allowed to use each denomination at most once. For instance, if the denominations are $\mathbf{1}\mathbf{,}\mathbf{}\mathbf{5}\mathbf{,}\mathbf{}\mathbf{10}\mathbf{,}\mathbf{}\mathbf{20}\mathbf{,}$then you can make change for $\mathbf{16}\mathbf{}\mathbf{=}\mathbf{}\mathbf{1}\mathbf{}\mathbf{+}\mathbf{}\mathbf{15}$and for $\mathbf{31}\mathbf{}\mathbf{=}\mathbf{}\mathbf{1}\mathbf{}\mathbf{+}\mathbf{}\mathbf{10}\mathbf{}\mathbf{+}\mathbf{}\mathbf{20}$but not for 40(because you can’t use 20 twice).

Input: Positive integers; ${\mathbf{x}}_{\mathbf{1}}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{,}{\mathbf{x}}_{\mathbf{n}}$another integer $\mathbf{v}$.

Output: Can you make change for $\mathbf{v}$, using each denomination${\mathbf{x}}_{\mathbf{i}}$ at most once?Show how to solve this problem in time $\mathbf{O}\left(\mathrm{nV}\right)$.

Short answer

The problem can also be solved by dynamic programming.

$\begin{array}{l}D\left(i,0\right)=\text{True}\\ \text{for}\left(i=0\text{\hspace{0.33em}to\hspace{0.33em}n}\right)\\ D\left(i,0\right)=\text{True}\\ \text{for}\left(i=1\text{\hspace{0.33em}to\hspace{0.33em}n}\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}for}\left(j=1\text{\hspace{0.33em}to\hspace{0.33em}V}\right)\end{array}$

$\begin{array}{l}\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}if}\left(\text{x}\left[i-1\right]\le j\right)\\ D\left(i,j\right)=\left(D\left(i-1,j-x\left[i-1\right]\right)\text{OR\hspace{0.33em}}D\left(i-1,j\right)\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}else}\\ D\left(i,j\right)=D\left(i-1,j\right)\\ \text{return\hspace{0.33em}}D\left(n,V\right)\end{array}$

Step-by-step solution

Defining the recurrence relation

Let the sub problem be $\mathrm{D}\left(\mathrm{n},\mathrm{V}\right)$.

A sub-problem$D\left(v-x_i\right)$ is made at each step, from unused denomination.

The possible cases are:

• $D\left(n-1,V-x_n\right)=\text{TRUE}$implies that coin of denomination $x{}_n$ is used to make value $V$, so $V-x_n$can be made using $n-1$number of coins. So, $D\left(n,V\right)$will also be true.
• $D\left(n-1,V\right)=\text{TRUE}$ implies that a coin with denomination $x{}_n$is not used to make value V and V can be made from$n-1$ coin, so$D\left(n,V\right)$ is true.
• If both above discussed cases are not true that means,$D\left(n,V\right)$ then V cannot be obtained from n coins.

Based on above conditions, the recurrence relation is as follows:

$D\left(n,V\right)=\left\{\begin{array}{c}1;ED\left(n-1,V-x_n\right)ORD\left(n-1,V\right)\\ 0;\text{otherwise}\end{array}\right.$

Determine an algorithm

The algorithm is given as follows:

Consider an array of coins

$\begin{array}{l}D\left(i,0\right)=\text{True}\\ \text{for}\left(i=0\text{\hspace{0.33em}to\hspace{0.33em}n}\right)\\ D\left(i,0\right)=\text{True}\\ \text{for}\left(i=1\text{\hspace{0.33em}to\hspace{0.33em}n}\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}for}\left(j=1\text{\hspace{0.33em}to\hspace{0.33em}V}\right)\end{array}$

$\begin{array}{l}\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}if}\left(\text{x}\left[i-1\right]\le j\right)\\ D\left(i,j\right)=\left(D\left(i-1,j-x\left[i-1\right]\right)\text{OR\hspace{0.33em}}D\left(i-1,j\right)\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}else}\\ D\left(i,j\right)=D\left(i-1,j\right)\\ \text{return\hspace{0.33em}}D\left(n,V\right)\end{array}$

Analyse the time complexity of an algorithm

The first loop runs for n times. There two nested loops takes nV times. Since, $n<<nV$

Thus, the runtime of the algorithm is $O\left(nV\right)$.