money.jpg
問題(基礎(chǔ)版)：
把100元兌換成1元，2元桩引，5元缎讼，10元，20元坑匠，50元的零錢血崭，共有多少種不同換法。
動(dòng)態(tài)規(guī)劃思想解析：
- 拆解子問題
下面以5元換成1,2,3元的零錢為例厘灼。T[(change),target]表示用零錢序列change組成target的所有方法夹纫。見下圖：
example.png
其中：
T1[(1,2)，5-0*3]可看作只用1和2元设凹、不用3元組成5元的方法數(shù)舰讹；
T2[(1,2)，5-1*3]可看作用1和2元闪朱、并且只用1個(gè)3元組成5元的方法數(shù)月匣；
T6[(1)，3]可看作用1元奋姿，只用1個(gè)2元锄开、并且不用3元組成5元的方法數(shù)；
T9[(1)称诗，0]可看作用1元院刁，只用1個(gè)2元、只用1個(gè)3元組成5元的方法數(shù)粪狼。
-
狀態(tài)轉(zhuǎn)移表達(dá)式：
problem.png - 邊界條件：
- M-nd不得小于0退腥，并且當(dāng)M-nd等于0時(shí)任岸，也就是說之前的選擇已經(jīng)組成了目標(biāo)，所以表達(dá)式結(jié)果為1狡刘。
- 如果表達(dá)式為T[(a),c]享潜，只有a可以被c整除，此表達(dá)式才為1嗅蔬，否則為0剑按。例如T[(2),5]=0,T[(2),6]=1。
Python3程序?qū)崿F(xiàn)
#遞歸實(shí)現(xiàn)
#根據(jù)邊界條件編寫程序
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
#計(jì)算結(jié)果
def Recursion(exlist,target):
structer=[[exlist,target]]
count=0
for jj in Dismantle(structer):#所有子問題的集合
if Solve(jj[0],jj[1])==1:#計(jì)算每一個(gè)子問題的結(jié)果
count+=Solve(jj[0],jj[1])
return count
print(Recursion([1,2,5,10,20,50],100))
結(jié)果：4562
上述的遞歸程序編寫較為復(fù)雜艺蝴，但是容易理解，下面給出基于動(dòng)態(tài)規(guī)劃的程序鸟废。
#動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)
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))
結(jié)果：4562
問題(進(jìn)階版)：
有面值為1元猜敢、3元和5元的錢幣若干張，如何用最少的錢幣湊夠11元盒延，并列出組合方法缩擂。
拆解子問題：
和基礎(chǔ)版問題相比，此題復(fù)雜之處在于最小值的計(jì)算添寺。詳細(xì)見下圖：
min.png
Python3程序?qū)崿F(xiàn)
#記錄
def DP_Min(exlist,target):
fan=[0]+[target]*target
record=['']*(target+1)
#存儲(chǔ)最后一位
lic=[]
for i in exlist:
for j in range(i,target+1):
if fan[j-i]!=target:#如果等于target胯盯，說明之前沒有數(shù)的結(jié)合可以達(dá)到這個(gè)數(shù)
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個(gè)%s '%(hu.count(j),j)
print(shuoming)
return 'Done'
ggg=DP_Min([1,3,5],11)
print(Handle(ggg[0],ggg[1]))
#結(jié)果：最少為3。組合方法：2個(gè)5 1個(gè)1
不定期更新计露，歡迎留言博脑，敬請(qǐng)關(guān)注!!!
