Question

Given an unlimited supply of coins of denominations, we wish to make change for a value ; that is, we wish to find a set of coins whose total value is . This might not be possible: for instance, if the denominations are and 10 then we can make change for 15 but not for 12. Give an dynamic-programming algorithm for the following problem.Input:,; .Question: Is it possible to make change for using coins of denominations ?

Short answer

The algorithm is as follows:

Create an array of size

$\begin{array}{l}D\left(0\right)=\text{True}\\ \text{for}\left(i=1\text{\hspace{0.33em}to\hspace{0.33em}}V\right)\\ D\left(i\right)=\text{False}\\ \text{for}\left(v=1\text{\hspace{0.33em}to\hspace{0.33em}}V\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(x_j\le v\right)\\ D\left(v\right)=\left(D\left(v\right)ORD\left(v-x_i\right)\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}else}\\ D\left(v\right)=\text{False}\\ \text{return\hspace{0.33em}}D\left(V\right)\end{array}$

Step-by-step solution

Define dynamic programming 

Dynamic programming is a paradigm used for writing algorithm which helps to solve some particular type of problems more efficiently by saving the solution of subproblems and using them to get the final solution. Rather than performing the same calculation again and again, the optimal solution to subproblems are calculated and stored.

Determine the subproblem

Consider$D\left(u\right)$ as sub-problem such that $u=\left\{1,\dots .,v\right\}$.

Thus, according to question,$D\left(u\right)$ is true if it is possible to make change for v using coins denomination.$x_1,x_2,\dots x_n$

$D\left(u\right)=\left\{\begin{array}{c}TRUE;\text{ifitispossibletomakechangefor}v\\ \text{FALSE};\text{otherwise}\end{array}\right.$

Now, taking$D\left(u\right)$ as sub-problem, if it is possible to make change for$v$ using denomination,$x_1,x_2,\dots x_n$then it is also possible to make change for by using same denomination with the coin.

The desired recursion is:

Here, ‘’ is the value for which we finding denomination.