# 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 = 
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, ).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
``````