Illustrate the execution of the Coin Change algorithm on n

Illustrate the execution of the Coin Change algorithm on n = 10 in
the system of denominations d(1) = 1, d(2) = 5, and d(3) = 8.

Solution

Here given, n=10 and the system denominations are d(1)=1, d(2)=5, d(3)=8.

We can solve this problem using greedy and dynamic method.

First lets try with greedy method.

Algorithm:

Coin_change(n, C[1..s])

Input: A nonnegative integer n and an array of coin denominations C

Output: Array F[1..m]

Start

for i 1 to s do

F[i] n/C[i]

n n mod S[i]

if n = 0 return F

else

return ”Solution does not exists”

This is the method using greedy algorithm. The average time complexity of this algorithm is order of m which is the size of the coin denomination array.

Next we will see the dynamic approach to solve this problem.

Dynamic Algorithm:

Dynamic_Coin_Change(n)

// Let S[m] be the minimum number of coins needed to make change for p cents.

S[< 0] =

S[0] = 0

for m = 2 to n

min =

for i = 1 to k

if (m di)

if (S[m di ]) + 1 < min)

min = S[m di ] + 1

coin = i

C[m] = min

F[m] = coin

This is the dynamic method to solve this problem. The average time complexity is order of nk.

As given in the question, the execution of the coin_change program can be like this:

1 * 1 + 2 * 5 + 3 * 8

So in this case we need  2 nickels of 5.