Coin Change, Part 2

May 21, 2013

In the previous exercise we studied the classic coin change problem to find all the ways to make a given amount of change using a given set of coins. Sometimes the problem in a different way: find the minimum set of coins needed to make a given amount of change. As with the prior exercise, sometimes the task is to find just the count and sometimes the task is to find the actual set of coins.

Your task is to write the two programs described above. 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 2”

  1. aks said

    Here is a Ruby solution to find the fewest number of coins adding to a given total:

    #!/usr/bin/env ruby
    # coin-change2.rb
    #
    # find the smallest number of coins (pennies, nickles, dimes, quarters) that
    # add to a specific total
    #
    # Find the numbers that fulfill 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
     
    class Array
      def sum
        self.reduce(:+)
      end
    end
     
    def compare(a,b)
      a == b ? 0 : a < b ? -1 : 1
    end
     
     
    if ARGV.size > 0
      total = ARGV.shift.to_i
    else
      total = 40
    end
     
    compute_max_coins(total)
    coin_sets = get_coin_sets(total)
     
    shortest_coin_set = coin_sets.sort!{|a,b| compare(a.sum, b.sum)}.first
     
    puts "For total = #{total}"
    puts "There are #{coin_sets.size} sets of coins"
     
    set = 1
    printf "Set  $.25  $.10  $.05  $.01  Coins\n"
    coin_sets.each do |q,d,n,p| 
      printf "%3d: %4d  %4d  %4d  %4d  %5d\n", set, q, d, n, p, [q,d,n,p].sum
      set += 1
    end
     
    printf "The smallest coin set has %d coins: %s\n", 
        shortest_coin_set.sum, 
        shortest_coin_set.join(", ")
    exit
    

    Here is the output:

    $ ./coin-change2.rb                                                                               
    For total = 40
    There are 31 sets of coins
    Set  $.25  $.10  $.05  $.01  Coins
      1:    1     1     1     0      3
      2:    1     0     3     0      4
      3:    0     4     0     0      4
      4:    0     3     2     0      5
      5:    0     2     4     0      6
      6:    1     1     0     5      7
      7:    0     1     6     0      7
      8:    1     0     2     5      8
      9:    0     0     8     0      8
     10:    0     3     1     5      9
     11:    0     2     3     5     10
     12:    0     1     5     5     11
     13:    0     0     7     5     12
     14:    1     0     1    10     12
     15:    0     3     0    10     13
     16:    0     2     2    10     14
     17:    0     1     4    10     15
     18:    0     0     6    10     16
     19:    1     0     0    15     16
     20:    0     2     1    15     18
     21:    0     1     3    15     19
     22:    0     0     5    15     20
     23:    0     2     0    20     22
     24:    0     1     2    20     23
     25:    0     0     4    20     24
     26:    0     1     1    25     27
     27:    0     0     3    25     28
     28:    0     1     0    30     31
     29:    0     0     2    30     32
     30:    0     0     1    35     36
     31:    0     0     0    40     40
    The smallest coin set has 3 coins: 1, 1, 1, 0
    
  2. aks said

    Of course, a more optimal solution is to just use the maximum value of each coin count (where the coin value * coin count is still less than the current total). Exercise left to others.. :-)

  3. Colin said

    As a note, the matrix solution is very similar in behavior to a recursive solution with memoization (as it is in general for most dynamic programming), and I usually prefer the recursive formulation.

    In clojure:

    (def best-pay
      (memoize (fn [coins amt]
        (if (zero? amt)
          []
          (let [cand (for [c (filter #(<= % amt) coins)]
                       (when-let [r (best-pay (filter #(<= % c) coins) (- amt c))]
                         (conj r c)))
                res (filter identity cand)]
            (when (seq res)
              (apply min-key count res)))))))
    
  4. Paul said

    This Python version returns the minimum number of coins and the change.

    import sys
    inf = sys.maxint     
    def min_coins(coins, amount):
        """return number of coins, list of coins"""
        C = [0] + [inf]  * amount
        S = [0] + [None] * amount
        for p in range(1, amount + 1):
            for c in coins:
                if c <= p and C[p - c] + 1 < C[p]:
                    C[p] = C[p - c] + 1
                    S[p] = c
        mincoins = []
        ind = -1
        while S[ind]:
            mincoins.append(S[ind])
            ind -= S[ind]
        return C[-1], mincoins
    
  5. brooknovak said

    In this case you can use a greedy algorithm, as aks said: keep selecting the largest coin possible until you reach your target change.

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 634 other followers

%d bloggers like this: