要改进这两种算法,都是一个目标,就是寻找不需要列出所有解的办法来。
前一种算法,是求出所有的可能解,然后再找其中的最优解。要进行优化,则可以将求解与求优合二为一。在每一个递归中,都寻找最优解。比如,make_change(14,[10,7,2]),我们就可以寻找14-10后剩余的4的最优解,得到[2,2],以及14-7后剩余的7的最优解,得到[7],最后是14-2后剩余的12的最优解,得到[10,2]。然后选择其中最短的一个[7],组合为[7,7]作为结果返回。
代码如下:
-
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
后一种算法,也可以相当直观的优化,因为整个求解的过程,是由少至多,因此,只要求到第一个满足要求的找零方案,就一定是最优解。
代码如下:
-
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
当然,这两个算法,都还有进一步优化的余地,咱们下回再说。
分享到:
相关推荐
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 5ssd3 practical quiz 5
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
ssd3 Practical Quiz 3 答案 ssd3 Practical Quiz 3 答案
ssd3 Practical Quiz 7 答案 ssd3 Practical Quiz 7 答案
ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5ssd3 practical quiz 5
2007卡耐基软件工程网路教材 ssd3 practical quiz3
ssd3 practical quiz 7ssd3 practical quiz 7ssd3 practical quiz 7ssd3 practical quiz 7
ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8ssd3 practical quiz 8
ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1ssd3 practical quiz 1 ssd3 practical quiz 1
这是卡耐基梅隆大学网上教材,面向对象程序设计(SSD3)练习三(quiz3)的答案。
ssD3 Practical Quiz 2 答案ssD3 Practical Quiz 2 答案ssD3 Practical Quiz 2 答案
2007卡耐基软件工程网路教材 ssd3 practical quiz2
卡耐基教程SSD3 quiz4的答案 卡耐基教程SSD3 quiz4的答案
SSD5 Multiple-Choice Quiz 3 SSD5 Multiple-Choice Quiz 3
ssd3 Practical Quiz 5 答案 ssd3 Practical Quiz 5 答案
ssd3 quiz2答案
卡耐基教程SSD3 quiz9的答案 卡耐基教程SSD3 quiz9的答案