Programming Praxis

Home | Pages | Archives

Coin Change, Part 1

May 17, 2013 9:00 AM

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 n − c 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.

Share this:

Posted by programmingpraxis

Categories: Exercises

Tags:

7 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 […]

    By Programming Praxis – Coin Change, Part 1 | Bonsai Code on May 17, 2013 at 3:06 PM

  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

    By Remco Niemeijer on May 17, 2013 at 3:06 PM

  3. Here is a Ruby program with both functions


    $ ./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

    view raw

    coin-change1 output

    hosted with ❤ by GitHub


    #!/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

    view raw

    coin-change1.rb

    hosted with ❤ by GitHub 

    #!/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

    By Alan S. on May 21, 2013 at 4:23 PM

  4. 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

    By aks on May 21, 2013 at 4:24 PM

  5. […] This post presents C# solutions to a coin change problem as described in https://programmingpraxis.com/2013/05/17/coin-change-part-1. […]

    By Programming Praxis – Coin Change, Part 1, C# Solutions | Software Salad on June 10, 2013 at 11:37 PM

  6. I have done this exercise using a simple method: I divide the total (T) by the first coin (C1). I take the integer part of this division (n1=T//c1). n1 represents the maximum number of possiblities of having c1 in any combinaison. After that, I do the same process for finding the total minus 0, 1,…, n1*c1 now using just the new set (C2, C3, C4).

    Here is the program in Python, and it works well: the result is outputed very fast.

    c1=25
    c2=10
    c3=29
    c4=3

    T=40

    C=[]
    for i in range(0, (T//c1)+1):
    if T-(ic1)==0:
    C.append([i,0,0,0])
    continue
    for j in range(0, ((T-i    c1)//c2)+1):
    if T-ic1-jc2==0:
    C.append([i,j,0,0])
    continue
    for w in range(0, ((T-ic1-jc2)//c3)+1):
    if (T-ic1-jc2-wc3)%c4 == 0:
    C.append([i,j,w,(T-i    c1-jc2-wc3)//c4])

    for i in C:
    print(i)
    print(len(C))

    By taoufik belaidi on October 15, 2019 at 10:42 AM

  7. […] solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be […]

    By Modified Coin Change | Programming Praxis on November 19, 2019 at 10:00 AM

Leave a Reply

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.