Making change

Problem statement: given an integer amount of money and a list of denominations of coins/bills in the currency, give the shortest list of coins/bills to compose the amount of money.

Example: given U.S. coins (25¢, 10¢, 5¢, 1¢) and the amount 57¢, it should return the list [25¢, 25¢, 5¢, 1¢, 1¢].

There are a number of solutions. The simplest solution is a naïve greedy algorithm that starts with the largest denomination. This works great with cases like U.S. denominations but fails for cases like make_change(14, [10, 7, 1]). The easiest correct solution is a naïve recursive one, which finds all solutions and then returns the shortest one, but it re-calculates solutions to the same problems over and over again, taking much longer than it ought to. Memoizing the recursive solution approaches an optimal solution, but the optimal solution is a dynamic programming solution which implements a breadth-first search of solutions sets, from 1-coin solutions on up, ensuring that the first solution found is the optimal one.

Here is an implementation in Ruby of the dynamic programming solution.


def make_change(total, denominations = [1, 5, 10, 25])
  results = []
  denominations.sort!
  current = [0]
  while subtotal = current.shift do
    denominations.each do |denomination|
      new_subtotal = subtotal + denomination
      next if new_subtotal > total or results[new_subtotal]
      results[new_subtotal] = denomination
      if new_subtotal == total
        solution = []
        while new_subtotal > 0 do
          coin = results[new_subtotal]
          solution << coin
          new_subtotal -= coin
        end
        return solution
      else
        current.push new_subtotal
      end
    end
  end
end

Here are some RSpec tests to verify the solution:


describe "#make_change" do
  it "returns nil when there is no solution" do
    make_change(-1).should be_nil
    make_change(1, []).should be_nil
    make_change(1.5, [2, 1]).should be_nil
    make_change(1, [2]).should be_nil
    make_change(7, [5, 3]).should be_nil
    make_change(1023, (1..10).map{ |n| 2**n }).should be_nil
  end

  it "creates change correctly for U.S. denominations by default" do
    make_change(57).should == [25, 25, 5, 1, 1]
  end

  it "creates change correctly for old English denominations" do
    make_change(48, [240, 60, 30, 24, 12, 6, 3, 1]).should == [24, 24]
  end
   
  it "should work with Swiss paper money" do
    money = [1000,500,200,100,50,20,10,5,2,1]
    make_change(1789, money).should == [1000,500,200,50,20,10,5,2,2]
  end

  it "should complete in a reasonable amount of time" do
    make_change(1000001, [1000000, 1]).should == [1000000, 1]
    make_change(10000001, [10000000, 1]).should == [10000000, 1]
    make_change(100000001, [100000000, 1]).should == [100000000, 1]
    make_change(1000001, [1000000, 2, 1]).should == [1000000, 1]
  end

  it "should solve some other complex scenarios" do
    make_change(14, [10, 7, 1]).should == [7, 7]
    make_change(14, [10, 7, 2]).should == [7, 7]
    make_change(24, [10, 8, 2]).should == [8, 8, 8]
    make_change(11, [10, 9, 2]).should == [9, 2]
    make_change(19, [5, 2, 1]).should == [5, 5, 5, 2, 2]
    make_change(39, [5, 2, 1]).should == [5, 5, 5, 5, 5, 5, 5, 2, 2]
    money = [97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3]
    make_change(101, money).should have(3).things
    make_change(4563, money).should have(49).things
  end
end

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 
To comment, click below to log in.