Play with Quiz — 找零钱(2)

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

找出符合要求的解,比较简单,先写在下面。
[cc lang=”ruby” css=”no”]
def get_best_change(change_list)
best_change=nil
min_length=100000
change_list.each do |list|
if list.lengthcoin
sub_change_list=get_all_change_list(amount-coin,coins)
sub_change_list.each do |list|
change_list.insert(-1,list.insert(-1,coin).sort)
end
end
if amount==coin
change_list.insert(-1,[coin])
end
end
return change_list
end
[/cc]

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

[cc lang=”ruby” css=”no”]
def get_all_change_list(amount,coins)
min_coin=coins[coins.length-1]
max_list_size=amount/min_coin+ ((amount%min_coin==0) ? 0 : 1)
change_list={}
coins.each do |coin|
change_list[[coin]]=coin
end
2.upto(max_list_size) do
new_change_list={}
coins.each do |coin|
change_list.each do |list,v|
new_change_list[list.clone.insert(list.length,coin).sort]=v+coin if v+coin<=amount end end change_list.merge!(new_change_list) end change_list.delete_if { |key,value| value!=amount } change_list.keys end [/cc] 写出这两个函数,也不容易,具体的思路,明天再讲解吧。未完待续。。。

发表评论

电子邮件地址不会被公开。