Coin Change, Part 1

May 17, 2013

It is a classic problem from computer science to determine the number of ways in which coins can be combined to form a particular target; as an example, there are 31 ways to form 40 cents from an unlimited supply of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), ranging from the 3-coin set (5 10 25) to the 40-coin set consisting only of pennies.

The solution is usually stated in recursive form: if c is the first coin in the set of coins cs and n is the target, the solution is the number of ways to reach the target after removing c from cs plus the number of ways to reach nc using all the coins in cs. The algorithm to make a list of the coins, instead of the count, is the same, but keeping track of the list of coins instead of the count.

Your task is to write two functions, one to determine the count and one to determine the list of coins. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

5 Responses to “Coin Change, Part 1”

  1. […] today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/17/programming-praxis-coin-change-part-1/ for a version with comments):

    import Data.List
    
    coins :: (Num a, Ord a) => [a] -> a -> [[a]]
    coins _  0 = [[]]
    coins xs n = [c:r | (c:cs) <- tails xs, c <= n, r <- coins (c:cs) (n-c)]
    
    count :: (Num a, Ord a) => [a] -> a -> Int
    count xs = length . coins xs
    
  3. Alan S. said

    Here is a Ruby program with both functions

    #!/usr/bin/env ruby
    # coin-change1.rb
    #
    # count sets of coins (pennies, nickles, dimes, quarters) that
    # add to a specific total
    #
    # Count the different sets of the polynomial: 
    #   total = P + N*5 + D*10 * Q*25
    # 
    # A "coin set" is a 4-tuple of [P,N,D,Q]
    #
     
    $coin_values = [ 1, 5, 10, 25 ]
     
    # given a total, find the maximum number of coins for each
    # denomination
     
    def compute_max_coins(total)
      $max_coins = $coin_values.map {|value| Integer(total / value)}
      $max_pennies  = $max_coins[0]
      $max_nickles  = $max_coins[1]
      $max_dimes    = $max_coins[2]
      $max_quarters = $max_coins[3]
    end
     
    # get all the coin sets for a given total
     
    def get_coin_sets(total)
      coin_sets = []
      (0..$max_quarters).each { |q|
        break if total < q*25
        qtotal = total - q*25
        (0..$max_dimes).each { |d|
          break if qtotal < d*10
          dtotal = qtotal - d*10
          (0..$max_nickles).each { |n|
            break if dtotal < n*5
            p = dtotal - n*5
            coin_sets += [[q,d,n,p]]
          }
        }
      }
      coin_sets
    end
     
    if ARGV.size > 0
      total = ARGV.shift.to_i
    else
      total = 40
    end
     
    compute_max_coins(total)
    coin_sets = get_coin_sets(total)
     
    puts "For total = #{total}"
    puts "There are #{coin_sets.size} sets of coins"
    puts ''
    set = 1
    printf "Set  $.25  $.10  $.05  $.01\n"
    coin_sets.each do |q,d,n,p| 
      printf "%3d: %4d  %4d  %4d  %4d\n", set, q, d, n, p
      set += 1
    end
     
    exit
    
  4. aks said

    Here is the output:

    $ ./coin-change1.rb 
    For total = 40
    There are 31 sets of coins
     
    Set  $.25  $.10  $.05  $.01
      1:    0     0     0    40
      2:    0     0     1    35
      3:    0     0     2    30
      4:    0     0     3    25
      5:    0     0     4    20
      6:    0     0     5    15
      7:    0     0     6    10
      8:    0     0     7     5
      9:    0     0     8     0
     10:    0     1     0    30
     11:    0     1     1    25
     12:    0     1     2    20
     13:    0     1     3    15
     14:    0     1     4    10
     15:    0     1     5     5
     16:    0     1     6     0
     17:    0     2     0    20
     18:    0     2     1    15
     19:    0     2     2    10
     20:    0     2     3     5
     21:    0     2     4     0
     22:    0     3     0    10
     23:    0     3     1     5
     24:    0     3     2     0
     25:    0     4     0     0
     26:    1     0     0    15
     27:    1     0     1    10
     28:    1     0     2     5
     29:    1     0     3     0
     30:    1     1     0     5
     31:    1     1     1     0
    
  5. […] This post presents C# solutions to a coin change problem as described in http://programmingpraxis.com/2013/05/17/coin-change-part-1. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 615 other followers

%d bloggers like this: