Coin Change

From Algorithmist
Jump to: navigation, search

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d_{1}\ldots d_{m}. 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 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? (For simplicity's sake, the order does not matter.)

It is more precisely defined as:

Given an integer N and a set of integers S=\{S_{1},S_{2},\ldots ,S_{m}\}, how many ways can one express N as a linear combination of S=\{S_{1},S_{2},\ldots ,S_{m}\} with non-negative coefficients?

Mathematically, how many solutions are there to N=\sum _{{k=1\ldots m}}{x_{k}S_{k}} where x_{k}\geq 0,k\in \{1\ldots m\}

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

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

Is there a solution for N=\sum _{{k=1\ldots m}}{x_{k}S_{k}} where x_{k}\geq 0,k\in \{1\ldots m\} (Is there a solution for integer N and a set of integers S=\{S_{1},S_{2},\ldots ,S_{m}\}?)

Is there a solution for N=\sum _{{k=1\ldots m}}{x_{k}S_{k}} where x_{k}\geq 0,k\in \{1\ldots m\},\sum _{{k=1\ldots m}}{x_{k}}\leq T (Is there a solution for integer N and a set of integers S=\{S_{1},S_{2},\ldots ,S_{m}\} such that \sum _{{k=1\ldots m}}{x_{k}}\leq T - using at most T coins)

Recursive Formulation[edit]

We are trying to count the number of distinct sets.

Since order does not matter, we will impose that our solutions (sets) are all sorted in non-decreasing order (Thus, we are looking at sorted-set solutions: collections).

For a particular N and S=\{S_{1},S_{2},\ldots ,S_{m}\} (now with the restriction that S_{1}<S_{2}<\ldots <S_{m}, our solutions can be constructed in non-decreasing order), the set of solutions for this problem, C(N,m), can be partitioned into two sets:

  • There are those sets that do not contain any S_{m} and
  • Those sets that contain at least 1 S_{m}

If a solution does not contain S_{m}, then we can solve the subproblem of N with S=\{S_{1},S_{2},\ldots ,S_{{m-1}}\}, or the solutions of C(N,m-1).

If a solution does contain S_{m}, then we are using at least one S_{m}, thus we are now solving the subproblem of N-S_{m}, S=\{S_{1},S_{2},\ldots ,S_{m}\}. This is C(N-S_{m},m).

Thus, we can formulate the following:

C(N,m)=C(N,m-1)+C(N-S_{m},m)

with the base cases:

  • C(N,m)=1,N=0 (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)
  • C(N,m)=0,N\leq 0 (no solution -- negative sum of money)
  • C(N,m)=0,N\geq 1,m\leq 0 (no solution -- we have money, but no change available)

Pseudocode[edit]

def count( n, m ):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m <= 0 and n >= 1: #m < 0 for zero indexed programming languages
        return 0
 
    return count( n, m - 1 ) + count( n - S[m], m )

Dynamic Programming[edit]

Note that the recursion satisfies the weak ordering R(n,m)<R(x,y)\iff n\leq x,m\leq y,(n,m)\neq (x,y). As a result, this satisfies the optimal-substructure property of dynamic programming.

The result can be computed in O(nm) 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
    for j from 0 to m
      if i equals 0
         table[i, j] = 1          
      else if j equals 0
         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]