greedy greedy algorithm

greedy_example.rb

#!/usr/bin/env ruby

# The challenge:
# Given a dollar amount, determine which bills to dispense, optimizing for fewest bills, using a greedy algorithm

# Ted Pennings, 2015, License: http://choosealicense.com/licenses/unlicense/


AVAILABLE_BILLS = [100, 50, 20, 10, 5, 1] # nobody wants $2 bills

amount = ARGV[0].to_i
raise ArgumentError, "You got no money. I don't understand #{ARGV[0]}. Please use positive integers" if amount < 1

puts "Dispensing $#{amount}"

dispensed = {}
AVAILABLE_BILLS.sort.reverse.each do |possible_bill|
  while (amount >= possible_bill) && (amount / possible_bill > 0)
    begin
      amount -= possible_bill
    ensure
      dispensed[possible_bill] ||= 0
      dispensed[possible_bill] += 1
    end
  end
end

dispensed.each do |bill, count|
  puts "$#{bill} bill: dispense #{count}"
end


# This algorithm is greedy because each iteration chooses to dispense the largest bills
# when possible. This decision is locally optimal, to dispense the most money, and therefore
# 'greediest' in computer science terms. Looping over the bills from largest to smallest
# is the main factor by which this works. Note that without $1 bills, it would eat money.

# Examples
#  $ ./greedy_example.rb 56
#  Dispensing $56
#  $50 bill: dispense 1
#  $5 bill: dispense 1
#  $1 bill: dispense 1
#
#  $ ./greedy_example.rb 147
#  Dispensing $147
#  $100 bill: dispense 1
#  $20 bill: dispense 2
#  $5 bill: dispense 1
#  $1 bill: dispense 2

# A more efficient, but less readable version of the algorithm is below:
# dispensed = {}
# AVAILABLE_BILLS.sort.reverse.each do |possible_bill|
#   if amount >= possible_bill
#     dispensed[possible_bill], amount = amount.divmod(possible_bill)
#   end
# end