Friday, December 6, 2013

Minimum coin change problem

Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount?

Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations
{1,1,4}
{1,1,1,3}
{3,3}
The minimum number of coins to make change for 6 is '2'.

This problem can be efficiently solved using dynamic programming approach. Let us formulate the problem in terms of it's sub-problems.

Let the amount be T and the given denominations are {d1,d2,...dn}. Create an array of size (T+1) denoted by MC[].
MC[K] denotes the minimum number coins required for amount K. It can be defined as follows

Min{ MC[K-d1], MC[K-d2],...MC[K-dn] } + 1 
This means that we can find the solution of a problem from it's sub-problems and it has optimal sub-structure property suggesting the dynamic programming solution. 

Following is the C++ implementation of the above algorithm.