Question

Here is yet another variation on the change-making problem (Exercise 6.17). Given an unlimited supply of coins of denominations ${\mathbf{x}}_{\mathbf{1}\mathbf{,}}{\mathbf{x}}_{\mathbf{2}\mathbf{,}}{\mathbf{x}}_{\mathbf{3}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathbf{x}}_{\mathbf{n}}$we wish to make change for a value v using at most k coins; that is, we wish to find a set of$\mathbf{\le }\mathbf{k}$coins whose total value is v. This might not be possible: for instance, if the denominations are 5 and 10 and k=6, then we can make change for 55 but not for 65. Give an efficient dynamic-programming algorithm for the following problem. Input: ; ${\mathbf{x}}_{\mathbf{1}\mathbf{,}}{\mathbf{x}}_{\mathbf{2}\mathbf{,}}{\mathbf{x}}_{\mathbf{3}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathbf{x}}_{\mathbf{n}}\mathbf{;}\mathbf{k}\mathbf{;}\mathbf{v}\mathbf{.}$Question: Is it possible to make change for v using at most k coins, of denominations ${\mathbf{x}}_{\mathbf{1}\mathbf{,}}{\mathbf{x}}_{\mathbf{2}\mathbf{,}}{\mathbf{x}}_{\mathbf{3}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathbf{x}}_{\mathbf{n}}\mathbf{?}$

Short answer

It may or may not be possible to make change for v using at most k coins,of denominations ${\mathrm{x}}_{1,}{\mathrm{x}}_{2,}{\mathrm{x}}_3.........{\mathrm{x}}_{\mathrm{n}}$

Step-by-step solution

Dynamic programming approach.

In dynamic programming there are all possibilities and more time as compared to greedy programming. and the Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

Define Recurrence Relation and define its Algorithm.

Let T(v) be the minimum number of coins needed.

We have ‘n’ number of coins of denomination, where we have check for the possibility to make a change for value v by taking at most k coins from given denominations.

The supply of coins of denominations ${\mathrm{x}}_{1,}{\mathrm{x}}_{2,}{\mathrm{x}}_3.........{\mathrm{x}}_{\mathrm{n}}$and to make change for a value v using at most k coins, that is, we wish to find a set of $\le k$coins whose total value. This might not be possible: for instance, if the denominations are 5 and 10 and k=6 then we can make change for 55 but not for 65.

To achieve this, we will create dynamic algorithm where first we need to find the least number of coins needed to get value v. After this, comparing it with ‘k’ coins to check if we can make value using k coins only.

So, the recurrence relation will be:

$$\begin{gathered} \mathrm{T}\left(\mathrm{v}\right)=\mathrm{MIN}\left\{\mathrm{MIN}\{\mathrm{T}\left(\mathrm{v}-\mathrm{x}\right)+1\right\};\mathrm{if}1\le \mathrm{i}\le \mathrm{n}, \\ \mathrm{T}\left(\mathrm{v}\right)=\infty ;\mathrm{otherwise}, \end{gathered}$$

Here ${\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3...........{\mathrm{x}}_{\mathrm{n}}$we take an array Change [] with v elements in it. This means the length of array Change [] will be v. We will take the value of each element as ‘infinity’. Here value at index ‘j’ will tell about the number of coins need to make value. So, when we trace index ‘v’, the algorithm will check if the value at index ‘v’ is less than ‘k’. to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

So, algorithm will return true if the condition is satisfied else, return false.