Wednesday, October 16, 2013

A closer look at Coin Change

Coin change has been a very famous computing problem which can be easily solved by Dynamic programming.

So what is coin change ?
If we want to make change for N cents, and we have infinite supply of each of S = \{ S_1, S_2, \ldots, S_m \} valued coins, how many ways can we make the change? (The order does not matter.)

For example, for N = 4,S = {1,2,3}, there are 7 possible solutions: {1,1,1,1},{1,1,2}, {1, 2, 1}, {2, 1, 1}, {2,2},{1,3}, {3, 1}.

So how to compute the number of ways efficiently?




Lets assume you know the number of ways to generate the sum 1, 2, 3 , can you find the number of  ways to generate 4?

Yes, you can, indeed you have just broken the problem into the subproblems, a basic paradigm of the dynamic programming.

Let assume F(n) denotes the number of solutions possible.
So F(4) = F(3) + F(2) + F(1)

In general if S[i] denotes the denominations of the coins then



The below piece of code generates the number of combinations for a particular sum.
int coin_change_infinite(int s[], int n, int val) {
    int * a = (int *) calloc(1, sizeof(int) * (val + 1));
    int res;
    sort(s, s + n);
    a[0] = 1;
    for(int i = 1; i <= val; i++)
         for(int j = 0; s[j] <= i && j < n; j++)
                 a[i] += a[i - s[j]];
    res = a[val];
    free(a);
    return res;
}


Overall running time for the algorithm is O(n*c) (n is the value for which the denominations needs to be made and c is the types of denominations available.) and space complexity is O(n)

2 comments :

  1. In the example that you've provided how come coming up with sum 7 is different between 1,1,2 and 1,2,1 (and other permutations as well)

    ReplyDelete
    Replies
    1. The problem statement clearly states that "the order does not matter".
      There is a easy modification which can be done if you wish to calculate only the unique combinations.
      For the above example the number of ways to have a sum of 4 with the give coins of 1, 2, 3 is 4 ways = {1,1,1,1},{1,1,2}, {2,2},{1,3}.

      Delete