Dynamic Programming

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)

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

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[ ]

1 | 2 | 3 | |

d[i] | 1 | 2 | 5 |

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.

0 | 1 | 2 | 3 | 4 | 5 | 6 | |

C[p] |

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.

0 | 1 | 2 | 3 | 4 | 5 | 6 | |

S[p] |

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.

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

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

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

0 | 1 | 2 | 3 | 4 | 5 | 6 | |

C[p] | 0 | 1 | 1 | 2 | 2 | 1 | 2 |

0 | 1 | 2 | 3 | 4 | 5 | 6 | |

S[p] | 0 | 1 | 2 | 1 | 2 | 3 | 1 |

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

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

```
#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 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.