python換零錢_Python3算法執行個體 1.2：動态規劃 之 換零錢

money.jpg

問題(基礎版)：

把100元兌換成1元，2元，5元，10元，20元，50元的零錢，共有多少種不同換法。

動态規劃思想解析：

拆解子問題

下面以5元換成1,2,3元的零錢為例。T[(change),target]表示用零錢序列change組成target的所有方法。見下圖：

example.png

其中：

T1[(1,2)，5-0*3]可看作隻用1和2元、不用3元組成5元的方法數；

T2[(1,2)，5-1*3]可看作用1和2元、并且隻用1個3元組成5元的方法數；

T6[(1)，3]可看作用1元，隻用1個2元、并且不用3元組成5元的方法數；

T9[(1)，0]可看作用1元，隻用1個2元、隻用1個3元組成5元的方法數。

狀态轉移表達式：

problem.png

邊界條件：

M-nd不得小于0，并且當M-nd等于0時，也就是說之前的選擇已經組成了目标，是以表達式結果為1。

如果表達式為T[(a),c]，隻有a可以被c整除，此表達式才為1，否則為0。例如T[(2),5]=0,T[(2),6]=1。

Python3程式實作

#遞歸實作

#根據邊界條件編寫程式

def Solve(exlist,target):

#判斷問題解

if target==0:

return 1

else:

if len(exlist)==1 and target%exlist[0]==0:

return 1

else:

return 0

#遞歸的方式，先将問題拆解為子問題的集合

def Dismantle(exlist):

if len(exlist[0][0])>1:

fu=[]

for ie in exlist:

for ji in range(int(ie[1]/ie[0][-1])+1):

fu.append([ie[0][0:-1],ie[1]-ji*ie[0][-1]])

return Dismantle(fu)

else:

return exlist

#計算結果

def Recursion(exlist,target):

structer=[[exlist,target]]

count=0

for jj in Dismantle(structer):#所有子問題的集合

if Solve(jj[0],jj[1])==1:#計算每一個子問題的結果

count+=Solve(jj[0],jj[1])

return count

print(Recursion([1,2,5,10,20,50],100))

結果：4562

上述的遞歸程式編寫較為複雜，但是容易了解，下面給出基于動态規劃的程式。

#動态規劃實作

def DP_Com(exlist,num):

an=[1]+[0]*num

for i in exlist :

for j in range(i,num+1):

an[j]+=an[j-i]

return an[num]

print(DP_Com([1,2,5,10,20,50],100))

結果：4562

問題(進階版)：

有面值為1元、3元和5元的錢币若幹張，如何用最少的錢币湊夠11元，并列出組合方法。

拆解子問題：

和基礎版問題相比，此題複雜之處在于最小值的計算。詳細見下圖：

min.png

Python3程式實作

#記錄

def DP_Min(exlist,target):

fan=[0]+[target]*target

record=['']*(target+1)

#存儲最後一位

lic=[]

for i in exlist:

for j in range(i,target+1):

if fan[j-i]!=target:#如果等于target，說明之前沒有數的結合可以達到這個數

fan[j]=min(fan[j-i]+1,fan[j])

#記錄

if fan[j-i]+1<=fan[j]:

record[j]=record[j-i]+'%d*'%i

else:

record[j]=record[j]

if record[-1]!='':

lic.append(record[-1])

if len(lic)==0:

return '無解'

else:

return lic,fan[target]

#處理字元串

def Handle(exstr,num):

for i in set(exstr):

hu=i.split('*')

hu=list(filter(lambda x:x,hu))#去除掉split留下的空格

if len(hu)==num:

shuoming=''

for j in set(hu):

shuoming+='%s個%s '%(hu.count(j),j)

print(shuoming)

return 'Done'

ggg=DP_Min([1,3,5],11)

print(Handle(ggg[0],ggg[1]))

#結果：最少為3。組合方法：2個5 1個1

不定期更新，歡迎留言，敬請關注!!!