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]作为结果返回。

代码如下：

1. def make_change(amount, coins = [25, 10, 5, 1])   
2.   return [amount] if coins.include?(amount)
3.   min_one_coin=nil
4.   min_coins=Array.new(amount)
5.   coins.each do |one_coin|
6.     if amount-one_coin>0
7.       other_coins=make_change(amount-one_coin,coins)   
8.       if other_coins && min_coins.size>other_coins.size   
9.         min_one_coin=one_coin   
10.         min_coins=other_coins
11.       end
12.     end
13.   end
14.   min_one_coin ? [min_one_coin]+min_coins : nil 
15. end

后一种算法，也可以相当直观的优化，因为整个求解的过程，是由少至多，因此，只要求到第一个满足要求的找零方案，就一定是最优解。
代码如下：

1. def make_change(amount, coins = [25, 10, 5, 1])
2.   change_list={}
3.   coins.each do |coin|
4.     return [amount] if amount==coin
5.     change_list[[coin]]=coin
6.   end
7.   while(true)
8.     new_change_list={}
9.     coins.each do |coin|
10.       change_list.each do |list,v|
11.         return list.insert(0,coin).sort  if coin+v==amount
12.         if v+coin<=amount
13.           new_list=list.clone.insert(list.length,coin).sort
14.           unless new_change_list[new_list]
15.             unless new_change_list.has_value?(v+coin)
16.               new_change_list[new_list]=v+coin
17.             end
18.           end
19.         end
20.       end
21.     end
22.     return nil if new_change_list.length==0
23.     change_list=new_change_list
24.   end
25. end

 

 

 

 

 

 

 

 

 

 

 

 

 

 

当然，这两个算法，都还有进一步优化的余地，咱们下回再说。