Coin Change

From Algorithmist

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 . It is a general case of Integer Partition, and can be solved with dynamic programming.

Contents 1 Overview 2 Recursive Formulation 2.1 Pseudocode 3 Dynamic Programming 4 Special Cases

[edit] Overview

The problem is typically asked as: If we want to make change for N 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 N and a set of integers , how many ways can one express N as a linear combination of with non-negative coefficients?

Mathematically, how many solutions are there to where

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 where (Is there a solution for integer N and a set of integers ?)

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

[edit] Recursive Formulation

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 (now with the restriction that , 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 does not contain any S_m,
• 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 , 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, . 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
• C(N,m) = 0,N < 0
• 

[edit] Pseudocode

func count( n, m )
  if ( n == 0 ) 
    return 1
  if ( n < 0 )
    return 0
  if ( m <= 0 and n >= 1 )
    return 0

  return count( n, m - 1 ) + count( n - S_m, m )

[edit] Dynamic Programming

Note that the recursion satisfies the weak ordering . As a result 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 )
  initialize table with base cases

  for i from 0 to n
    for j from 0 to m
      table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ]

  return table[ n, m ]

[edit] Special Cases

There are cases where the greedy algorithm is optimal - for example, the US coin system.

Failure of Greedy Approach
Consider the denominations 25,20,10,5
We have to form 40 in minimum number of coins.
Applying greedy approach , we would select 25,10,5 in that order requiring 3 coins.
But we can see that the optimal solution is in fact using two coins of 20.
This is an example where greedy choice fails.

Applicability of Greedy Approach
Consider the denominations 25,10,5. Using greedy approach in this case to calculate the minimum number of coins will work out always.