Skip to content

Instantly share code, notes, and snippets.

@rachelmyers
Created April 8, 2012 21:54
Show Gist options
  • Save rachelmyers/2340042 to your computer and use it in GitHub Desktop.
Save rachelmyers/2340042 to your computer and use it in GitHub Desktop.
Make Change
def greedy_make_change(num)
denominations = [50, 25, 10, 1]
change = []
while num > 0
denominations.each do |denomination|
if num - denomination >= 0
num -= denomination
change << denomination
break
end
end
end
change
end
p greedy_make_change(56)
def charitable_make_change(num)
return [] if num == 0
denominations = [50, 25, 10, 1]
options = denominations.map do |denomination|
remainder = num - denomination
[denomination, *charitable_make_change(remainder)] if remainder >= 0
end
options.compact.sort_by(&:size)[0]
end
p charitable_make_change(30)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment