2008-05-03

Play with Quiz — 找零钱(2)

接着上回的讨论，我们需要写两个方法，一个找出所有的零钱组合，get_all_change_list。另一个从中再找出符合要求的一个解。

找出符合要求的解，比较简单，先写在下面。

  1. def get_best_change(change_list)
  2.   best_change=nil
  3.   min_length=100000
  4.   change_list.each do |list|
  5.     if list.length<min_length
  6.       best_change=list
  7.       min_length=list.length
  8.     end
  9.   end
  10.   return best_change
  11. end

至于找到所有的解，就比较麻烦，从思路上来说，可以有两个方向，一个是做减法，一个是做加法。所谓减法，就是假设需要兑换15元的零钱，我就先考虑第一个硬币用10元，接下来就求解剩下5元的找零解法。这就是一个非常自然的，递归求解的思路。代码如下：

  1. def get_all_change_list(amount,coins)
  2.   change_list=[]
  3.   coins.each do |coin|
  4.     if amount>coin
  5.       sub_change_list=get_all_change_list(amount-coin,coins)
  6.       sub_change_list.each do |list|
  7.         change_list.insert(-1,list.insert(-1,coin).sort)
  8.       end
  9.     end
  10.     if amount==coin
  11.       change_list.insert(-1,[coin])
  12.     end
  13.   end
  14.   return change_list
  15. end

还有一种做加法的思路，是从所有硬币能够完成的组合来罗列。假设[25,10,5,1]这样一个组合，那么一枚硬币的组合方式，就只有4中，分别是[25],[10],[5],[1]，那么两枚硬币的组合方式自然就是，[25,25],[25,10],[25,10]….[1,5],[1,1]。一共16种，取掉次序不同的，一共有10种。再给出所有零钱组合的基础上，再寻找符合amount的找零组合即可。代码如下：

  1. def get_all_change_list(amount,coins)
  2.   min_coin=coins[coins.length-1]
  3.   max_list_size=amount/min_coin+ ((amount%min_coin==0) ? 0 : 1)
  4.   change_list={}
  5.   coins.each do |coin|
  6.     change_list[[coin]]=coin
  7.   end
  8.   2.upto(max_list_size) do
  9.     new_change_list={}
  10.     coins.each do |coin|
  11.       change_list.each do |list,v|
  12.         new_change_list[list.clone.insert(list.length,coin).sort]=v+coin if v+coin<=amount
  13.       end
  14.     end
  15.     change_list.merge!(new_change_list)
  16.   end
  17.   change_list.delete_if { |key,value| value!=amount }
  18.   change_list.keys
  19. end

写出这两个函数，也不容易，具体的思路，明天再讲解吧。未完待续。。。

评论
发表评论

您还没有登录，请登录后发表评论

庄表伟
搜索本博客
我的相册
B5998f8e-0b53-4830-ae9e-da1c6fa20ddc-thumb
匪夷所思
共 19 张
存档
最新评论