Play with Quiz — 找零钱 (3)

要改进这两种算法，都是一个目标，就是寻找不需要列出所有解的办法来。

前一种算法，是求出所有的可能解，然后再找其中的最优解。要进行优化，则可以将求解与求优合二为一。在每一个递归中，都寻找最优解。比如，make_change(14,[10,7,2])，我们就可以寻找14-10后剩余的4的最优解，得到[2,2]，以及14-7后剩余的7的最优解，得到[7]，最后是14-2后剩余的12的最优解，得到[10,2]。然后选择其中最短的一个[7]，组合为[7,7]作为结果返回。

代码如下：
[cc lang=”ruby” css=”no”]
def make_change(amount, coins = [25, 10, 5, 1])
return [amount] if coins.include?(amount)
min_one_coin=nil
min_coins=Array.new(amount)
coins.each do |one_coin|
if amount-one_coin>0
other_coins=make_change(amount-one_coin,coins)
if other_coins && min_coins.size>other_coins.size
min_one_coin=one_coin
min_coins=other_coins
end
end
end
min_one_coin ? [min_one_coin]+min_coins : nil
end
[/cc]

后一种算法，也可以相当直观的优化，因为整个求解的过程，是由少至多，因此，只要求到第一个满足要求的找零方案，就一定是最优解。
代码如下：
[cc lang=”ruby” css=”no”]
def make_change(amount, coins = [25, 10, 5, 1])
change_list={}
coins.each do |coin|
return [amount] if amount==coin
change_list[[coin]]=coin
end
while(true)
new_change_list={}
coins.each do |coin|
change_list.each do |list,v|
return list.insert(0,coin).sort if coin+v==amount
if v+coin<=amount new_list=list.clone.insert(list.length,coin).sort unless new_change_list[new_list] unless new_change_list.has_value?(v+coin) new_change_list[new_list]=v+coin end end end end end return nil if new_change_list.length==0 change_list=new_change_list end end [/cc] 当然，这两个算法，都还有进一步优化的余地，咱们下回再说。