Coin Change

From Algorithmist
Jump to navigation Jump to search

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, , using a given set of denominations . It is a general case of Integer Partition, and can be solved with dynamic programming. (The Min-Coin Change is a common variation of this problem.)

Overview[edit]

The problem is typically asked as: If we want to make change for cents, and we have infinite supply of each of valued coins, how many ways can we make the change? (For simplicity's sake, the order does not matter.)

It is more precisely defined as:

Given an integer and a set of integers , how many ways can one express as a linear combination of with non-negative coefficients?

Mathematically, how many solutions are there to where

For example, for , there are four solutions: .

Other common variations on the problem include decision-based question, such as:

Is there a solution for where (Is there a solution for integer and a set of integers ?)

Is there a solution for where (Is there a solution for integer and a set of integers such that - using at most coins)

Recursive Formulation[edit]

We are trying to count the number of distinct sets.

The set of solutions for this problem, , can be partitioned into two sets:

  • There are those sets that do not contain any and
  • Those sets that contain at least 1

If a solution does not contain , then we can solve the subproblem of with , or the solutions of .

If a solution does contain , then we are using at least one , thus we are now solving the subproblem of , . This is .

Thus, we can formulate the following:

with the base cases:

  • (one solution -- we have no money, exactly one way to solve the problem - by choosing no coin change, or, more precisely, to choose coin change of 0)
  • (no solution -- negative sum of money)
  • (no solution -- we have money, but no change available)

Pseudocode[edit]

def count( n, m ):
    if n < 0 or m <= 0: #m < 0 for zero indexed programming languages
        return 0
    if n == 0: # needs be checked after n & m, as if n = 0 and m < 0 then it would return 1, which should not be the case.
        return 1

    return count( n, m - 1 ) + count( n - S[m], m )

Dynamic Programming[edit]

Note that the recursion satisfies the weak ordering . As a result, this satisfies the optimal-substructure property of dynamic programming.

The result can be computed in time - the above pseudocode can easily be modified to contain memoization. It can be also rewritten as:

func count( n, m )

  for i from 0 to n+1
    for j from 0 to m
      if i equals 0
         table[i, j] = 1          
      else if j equals 0
         if i%S[j] equals 0
               table[i, j] = 1  
         else 
               table[i, j] = 0;
      else if S[j] greater than i
         table[i, j] = table[i, j - 1]
      else 
         table[i, j] = table[i - S[j], j] + table[i, j-1]

  return table[n, m-1]