Last active
August 29, 2015 14:24
-
-
Save tedpennings/965b5c4aeb2b6d1a88dd to your computer and use it in GitHub Desktop.
greedy greedy algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment