接着上回的讨论,我们需要写两个方法,一个找出所有的零钱组合,get_all_change_list。另一个从中再找出符合要求的一个解。
找出符合要求的解,比较简单,先写在下面。
-
def get_best_change(change_list)
-
best_change=nil
-
min_length=100000
-
change_list.each do |list|
-
if list.length<min_length
-
best_change=list
-
min_length=list.length
-
end
-
end
-
return best_change
-
end
至于找到所有的解,就比较麻烦,从思路上来说,可以有两个方向,一个是做减法,一个是做加法。所谓减法,就是假设需要兑换15元的零钱,我就先考虑第一个硬币用10元,接下来就求解剩下5元的找零解法。这就是一个非常自然的,递归求解的思路。代码如下:
-
def get_all_change_list(amount,coins)
-
change_list=[]
-
coins.each do |coin|
-
if amount>coin
-
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
还有一种做加法的思路,是从所有硬币能够完成的组合来罗列。假设[25,10,5,1]这样一个组合,那么一枚硬币的组合方式,就只有4中,分别是[25],[10],[5],[1],那么两枚硬币的组合方式自然就是,[25,25],[25,10],[25,10]….[1,5],[1,1]。一共16种,取掉次序不同的,一共有10种。再给出所有零钱组合的基础上,再寻找符合amount的找零组合即可。代码如下:
-
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
写出这两个函数,也不容易,具体的思路,明天再讲解吧。未完待续。。。
分享到:
相关推荐
ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2ssd3 practical quiz 2
ssd2 quiz2 答案全解,很全很可靠
ssD3 Practical Quiz 2 答案ssD3 Practical Quiz 2 答案ssD3 Practical Quiz 2 答案
2007卡耐基软件工程网路教材 ssd3 practical quiz2
ssd3 quiz2答案
U2 Language Quiz.docx
SSD5 Multiple-Choice Quiz 2 SSD5 Multiple-Choice Quiz 2 SSD5 Multiple-Choice Quiz 2
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
这是SSD4Multiple-Choice Quiz 2的详尽答案
ssd3 Practical Quiz 7 答案 ssd3 Practical Quiz 7 答案
SSD7 全部QUIZ答案,包含卡耐基梅隆网站上的全部quiz答案。想要选择题答案的看过来
ssd6 Practical Quiz 2答案!!!
Best of Ruby Quiz
SSD2 Multiple-Choice Quiz 1
ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3ssd3 practical quiz 3
卡耐基教程SSD3 quiz3的答案 卡耐基教程SSD3 quiz3的答案
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
ssd3 practical quiz 7ssd3 practical quiz 7ssd3 practical quiz 7ssd3 practical quiz 7
SSD4完整的Quiz答案,可做考试前的复习资料
ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8