Ruby每周一测 - 找零钱

Ruby每周一测 - Ruby Quiz 是Ruby Talk邮件列表上的一个持续了很长时间活动，每周有一个小题目被提出来，然后大家进行解答讨论。Amazon上还有相关的书： Best of Ruby Quiz。我尝试挑选其中的一些题目进行翻译，做一个每周一测系列，欢迎大家参与讨论。

-----题目分割线-----

这周的题目是找零钱，假设我们需要找给别人39美分的零钱，那么结果将会是(美元的硬币有25,10,5,1这种)：

>> make_change(39)
=> [25, 10, 1, 1, 1, 1]

假设我们的硬币种类有10,7,1，那么找14美分的零钱结果将会是：

>> make_change(14, [10, 7, 1])
=> [7, 7]

这次的每周一测就是完成该方法：

def make_change(amount, coins = [25, 10, 5, 1])

end

这个方法应该返回最优化的结果，即总的零钱个数最少。
另外，为了编程方便，这里假设coins已经是排序完毕的，并且如果无解的话，返回nil： make_change(5, coins = [4,2]) => nil


-----解答分割线-----
原题和一些解法在这里：http://rubyquiz.com/quiz154.html
原文的解答说明简单翻译见：http://www.javaeye.com/post/501439

贴一个solution, 不是最优

def make_change(money, changes=[25,10,5,1])
  already = []
  make_change_interal(money, changes, already)
  return already
end
def make_change_interal(money, changes, already)
  #decide if we can directly change money for changes
  if changes.include?(money)#money == changes[0]
    return already.push(money) #aleady the most optimal solution
  else
    #try each changes one, which larger than money
	to_try = changes.select {|x| x < money}
	#puts "to_try is #{to_try.inspect}"
	if to_try.size == 0 #&& money !=0 , we failed
	  return false
	end
	max = 9999
	#should backup the already, backtrace if necessary.
	change = changes[0]
	already_backup = already.dup
	 to_try.each do |x|
	  already0 = already_backup.dup
	  if make_change_interal(money - x, changes, already0.push(x))
	    if max > already0.size
		  
		  max = already0.size
		  already.replace(already0) #etc.
		  #change = x
		  #puts "max is #{max}, already0 is #{already0.inspect}"
		end
	  end
	  #and compare the result size. #and should cut out which definitely impossible route.
	end
	
    return true
  end
end
p make_change(25) #=>[25]
p make_change(10) #=>[10]
p make_change(1) #=>[1]
p make_change(39) #=> [25, 10, 1, 1, 1, 1] 

p make_change(26)
p make_change(27)
p make_change(14, [10, 7, 1])   

我也贴一个上来。

def make_change(amount, coins = [25, 10, 5, 1])
  first_coins=coins.select {|x| x <= amount}
  min_one_coin=nil
  min_coins=Array.new(amount,1)
  first_coins.each do |one_coin|
    other_coins=make_change(amount-one_coin,coins.select {|x| x <= one_coin})
    if min_coins.size>other_coins.size
      min_one_coin=one_coin
      min_coins=other_coins
    end
  end
  min_one_coin ? [min_one_coin]+min_coins : min_coins
end

p make_change(39)
p make_change(14, [10, 7, 1])

老庄的方法跑 make_change(14, [5,3,2]) 会出错

对的，通常的找零钱，一定会有解，所以一定会有一个1。

如果你的零钱中，最小的是2，那么输入1，就肯定会错。

比如 make_change(5,[7,2])

这样的题目，本身就是错的。

嗯，假如无解的话，可以返回nil，我已经修改题目，添加了这个说明
但是make_change(14, [5,3,2]) 是有解的，只是你那个解法算出来的不正确。

修订版

def make_change(amount, coins = [25, 10, 5, 1])
  return [amount] if coins.include?(amount)
  first_coins=coins.select {|x| x <= amount}
  min_one_coin=nil
  min_coins=Array.new(amount)
  first_coins.each do |one_coin|
    other_coins=make_change(amount-one_coin,coins.select {|x| x <= one_coin})
    if other_coins && min_coins.size>other_coins.size
      min_one_coin=one_coin
      min_coins=other_coins
    end
  end
  min_one_coin ? [min_one_coin]+min_coins : nil
end

凑个热闹，错误的贪心法！

def make_change(account, coins = [25, 10, 5, 1])
	solution = []
	current_account = account
	coins.each { |coin|
	
		break if current_account == 0
		
		if current_account >= coin
			number = current_account / coin
			current_account -= coin * number
			number.times { solution << coin }
		elsif coin == coins.last
			solution = nil
			break
		end
	}
	solution
end

to:姜太公

注意：应该返回最优化的结果，即总的零钱个数最少。
并且如果无解的话，返回nil

你的程序，有bug。

def make_change(amount, coins = [25, 10, 5, 1])
	change = []
	coins.each do |coin|
		(amount / coin).times do
			change << coin
			amount -= coin
		end
	end
	change if amount.zero?
end

p make_change(39) #[25, 10, 1, 1, 1, 1]
p make_change(14, [10, 7, 1]) #[10, 1, 1, 1, 1]
p make_change(14, [5, 3, 2]) #nil
p make_change(12, [22, 3, 2]) #[3, 3, 3, 3]