Coin Changing Problem

In this tutorial we will learn about Coin Changing Problem using Dynamic Programming.

In this problem our goal is to make change for an amount using least number of coins from the available denominations.

Example

Say I went to a shop and bought 4 toffees. It cost me Rs. 4 in total. So, I gave Rs. 10 to the shopkeeper.

The shopkeeper had Rs. 1 coins, Rs. 2 coins and Rs. 5 coins with him.
Now, the goal is: The shopkeeper has to make change for Rs. 6 using least number of coins from the available denominations coins (1, 2 and 5)

Assumptions

The shopkeeper has enough number of coins for the mentioned denomination so that he can make changes.

Solving this problem

The shopkeeper will make change for an amount Rs. 6
So, we can write A = 6

Available denominations are Rs. 1 coins, Rs. 2 coins and Rs. 5 coins.
So, total no. of different denominations n = 3

We can represent the denominations using an array d[ ]

where d[1] < d[2] < d[3] and range of array index i for the denomination array d[ ] is 1 <= i <= n

We have the following values and array

A = 6
n = 3
1 <= i <= n
0 <= p <= A

We will create an array C[ ] having A+1 elements.

The C[p] denotes the minimum number of coins required to make change for an amount p using given denomination coins.

Where, 0 <= p <= A

We have, A = 6
So, our array C will have (6+1) i.e., 7 elements.

We will create an array S[ ] having A+1 elements.

The S[p] will contain the index of the first coin in an optimal solution for making change of an amount p.

Where, 0 <= p <= A

We have, A = 6
So, our array S will have (6+1) i.e., 7 elements.

Formula

To solve this problem we will use the following formula

C[p] denotes the minimum number of coins required to make change for an amount p using given denomination coins d[i] where selected denomination is not greater than the amount p.

Steps

We will find the minimum no. of coins required for the amount p where p = 1, 2, ..., A
A is the amount for which we are making the change.

For every p we will first set min. no. of coins required i.e., min = INFINITY
This means we initially don’t know how many coins will be needed.

Then we check each denomination coins and see if it can be used to get the solution.

If its possible then we update the min and coin variables.
where, min = minimum no. of coins required for making change for amount p
coin = first index of the coin in the solution
else we move on

Formula

if d[i] <= p then
  if 1 + C[p - d[i]] < min then
    min = 1 + C[p - d[i]]
    coin = i

Solution

After solving this we will get the following values in the C and S array

Minimum number of coins

To find the min. no. of coins for amount Rs. 6 we have to take the value from C[p] array.

So, minimum coins required to make change for amount Rs. 6 = C[6] = 2

Coins in the optimal solution

To know the coins selected to make the change we will use the S[p] array

Step 1: Set a = A
Step 2: If a > 0 then

          Print d[S[a]]
        else STOP
Step 3: Set a = a - d[S[a]]

        Repeat step 2

Initially, a = 6
is a > 0
i.e., 6 > 0
YES
Print d[S[a]] = d[S[6]] = d[1]
i.e, Print 1
Set a = a - d[S[a]] = 6 - 1 = 5

So, the first coin is 1

Now, a = 5

is a > 0
i.e., 5 > 0
YES
Print d[S[a]] = d[S[5]] = d[3]
i.e, Print 5
Set a = a - d[S[a]] = 5 - 5 = 0

So, the second coin is 5

And now a = 0
so, we STOP

Answer

Therefore, to make change of amount Rs. 6 the shopkeeper will need minimum 2 coins and the coins will be Rs. 1 and Rs. 5

Code

#include <stdio.h>

//infinity: actually a very large number
#define INF 999

//total different denominations of coins available
#define N 3

//amount for which we are making change
#define A 6

void display(int arr[A+1]);
void coinChange(int d[N+1], int C[A+1], int S[A+1]);
void coinSet(int d[N+1], int S[A+1]);

int main(void) {
  //denomination d of the coins
  //we will start from index 1
  //so, index 0 is set to 0
  int d[N+1] = {0, 1, 2, 5};
  
  //Minimum number of coins required to make change
  int C[A+1];
  
  //S contain the index of the coin to be included
  //in the optimal solution
  int S[A+1];
  
  //compute minimum number of coins required
  coinChange(d, C, S);
  
  //display the content of the C array
  printf("\nC[p]\n");
  display(C);
  
  //display the content of the S array
  printf("\nS[p]\n");
  display(S);

  //display the minimum number of coins required to
  //make change for amount A
  printf("\nMin. no. of coins required to make change for amount %d = %d\n", A, C[A]);
  
  //display the coins used in the optimal solution
  printf("\nCoin Set\n");
  coinSet(d, S);
    
  return 0;
}

void coinChange(int d[N+1], int C[A+1], int S[A+1]) {
  int i, p, min, coin;
  
  //when amount is 0
  //then min coin required is 0
  C[0] = 0;
  S[0] = 0;
  
  for(p = 1; p <= A; p++) {
    min = INF;
    for(i = 1; i <= N; i++) {
      if(d[i] <= p) {
        if(1 + C[p - d[i]] < min) {
          min = 1 + C[p - d[i]];
          coin = i;
        }
      }
    }
    C[p] = min;
    S[p] = coin;
  }
}

void coinSet(int d[N+1], int S[A+1]) {
  int a = A;
  while(a > 0) {
    printf("Use coin of denomination: %d\n", d[S[a]]);
    a = a - d[S[a]];
  }
}

void display(int arr[A+1]) {
  int c;
  for(c = 0; c <= A; c++) {
    printf("%5d", arr[c]);
  }
  printf("\n");
}

Time Complexity

Time complexity of this algorithm is O(nA) where n is the total number of different denomination of the coins and A is the amount for which we are making change.