問題描述
現(xiàn)實生活中經(jīng)常遇到找零錢的問題决采。假設(shè)去超市購物買了一個售價為3毛7分的商品自沧，你給售貨員1元（1元 = 100分）錢混卵，售貨員需要找錢給你酥夭。假設(shè)有四種面額的硬幣：1分、5分遮精、1毛移迫、5毛旺嬉，每種硬幣的數(shù)量充足。現(xiàn)在要求售貨員使用最少數(shù)量的硬幣厨埋， 求出這個最少數(shù)量是多少邪媳。
也就是求一個數(shù)63，可以由集合 {1 , 5 ,10 ,50 }中任意元素任意數(shù)量組成荡陷，求最少數(shù)量雨效。
求解思路
- 思路一：根據(jù)日常生活經(jīng)驗，我們找零時候會從面額最大的開始湊废赞，如找63元徽龟，會先選擇50元，然后選10元唉地，最后選3個1元据悔。但這個方法并不能保證零錢的數(shù)量最少。例如耘沼，假設(shè)零錢面額為{1,20,50},需要找的是60极颓，按照剛才的方法，先選50群嗤，然后選10個1菠隆，零錢的數(shù)量為10。但是最優(yōu)解卻是選3個20。
- 思路二：以上方法為貪心算法骇径，每次計算局部解只選擇一條路徑來計算躯肌。 為了求最優(yōu)解則會遍歷所有的計算路徑，因此使用動態(tài)規(guī)劃來求解比較合適既峡。
首先找出子問題羡榴。
例如為了湊足零錢63碧查，需要求解的子問題有 62(63 -1),58(63 -5) , 53(63 -10) 13(63 -50)的最少硬幣數(shù)量运敢。然后取其中最少的那個解。
需要找的零錢數(shù)量為amount , 硬幣面額為 coins {c1,c2,c3...cN }忠售。
最少硬幣數(shù)量遞推方程為 :
m(x) = min{m(x-ci)+1 } x-ci>=0
m(0) = 0
m(1) = 1
講完思路后上代碼传惠。
遞歸程序
使用遞歸來寫這個程序比較簡單。
- 找出遞歸基的臨界狀態(tài)稻扬。
- 利用剛才遞推方程遞歸調(diào)用選擇最優(yōu)解卦方。
def rec_min_coins(amount,coins):
min_ret = amount
if not coins:
return 0
if amount ==1:
return 1
if amount <= 0:
return 0
else:
for c in coins:
if amount >= c:
min_count = rec_min_coins(amount-c,coins)+1
if min_count < min_ret: #選出最小的結(jié)果
min_ret = min_count
return min_ret
values = [1,5,10,25]
import time
start = time.time()
print(rec_min_coins(63,values))
end = time.time()
print(end-start)
out:6 104.87529873847961
運行遞歸程序耗費了104秒，中間一度還以為程序死循環(huán)了泰佳。
經(jīng)過分析以上程序時間復(fù)雜度為O(n)=4^n 也就是4^63盼砍，可想而知其性能是多么糟糕，下面通過動態(tài)規(guī)劃來優(yōu)化性能逝她。
動態(tài)規(guī)劃程序
用動態(tài)規(guī)劃方法浇坐，從狀態(tài)0開始計算并且把結(jié)果保存到一個數(shù)組里面，以避免子問題重復(fù)計算黔宛。
def dp_min_coins(amount,coins):
mins = [0 for x in range(amount+1)]
for i in range(1,amount+1):
min_ret = i
for c in coins:
if i >=c:
min_count =mins[i-c]+1
if min_count < min_ret:
min_ret = min_count
mins[i] = min_ret
return mins[amount]
values = [1,5,10,25]
import time
start = time.time()
print(dp_min_coins(63,values))
end = time.time()
print(end-start)
out:6
0.0010821819305419922
可以看到動態(tài)規(guī)劃運行時間不到1秒近刘。
總結(jié)
遇到求最優(yōu)解問題時，通惩位危可以用動態(tài)規(guī)劃或者遞歸來求解觉渴。但由于遞歸法求解過程中需要計算大量重復(fù)的子問題 ，其時間復(fù)雜度 O(n)=C^n徽惋。因此往往會優(yōu)先采用性能更好的動態(tài)規(guī)劃法案淋。
