第7章，動(dòng)態(tài)規(guī)劃，Dynamic Programming
　　又是動(dòng)態(tài)規(guī)劃，上一次想整理動(dòng)態(tài)規(guī)劃，結(jié)果還沒有整理完，實(shí)際上是沒有整理的動(dòng)力了，整理一道題都好費(fèi)時(shí)間的。
　　現(xiàn)在又要整理，這次能整理多少了？已經(jīng)開始寫了，那至少有些成果吧。

　　最長(zhǎng)公共子序列問題
　　書上例題，先簡(jiǎn)單分析一下，然后看與之類似的一個(gè)問題。
　　給出兩個(gè)長(zhǎng)度為n和m的字符串A=a1a2..an和B=b1b2..bm，確定A和B的最長(zhǎng)公共子序列的長(zhǎng)度。其中，子序列的定義是形式為ai1,ai2,..aik的字符串，ij滿足1<i1<i2<..<ik<n，也就是沒有要求子序列是元字符串中連續(xù)的字符序列。
　　為了使用動(dòng)態(tài)規(guī)劃技術(shù)，就需要找到最長(zhǎng)公共子序列長(zhǎng)度的遞推公式。令L(i,j)表示A的前i個(gè)字符和B的前j個(gè)字符中最大公共子序列長(zhǎng)度，如果i或j為0，那么L(i,j)=0，這是初始條件。當(dāng)ai=bj時(shí)，最長(zhǎng)公共子序列長(zhǎng)度應(yīng)該增加1，當(dāng)ai!=bj時(shí)呢？
　　　　　　i-1 　　　　 　　 i
j-1 　　　　 L(i-1,j-1) 　　 L(i,j-1)
j 　　　　　?L(i-1,j) 　　　?if ai=bj, 　　L(i,j)=L(i-1,j-1)+1
　　　　　　　　　　　　　else, 　　　?L(i,j)=max(L(i,j-1),L(i-1,j))
　　這就是動(dòng)態(tài)規(guī)劃二維矩陣的遞推關(guān)系。有了這個(gè)之后，求出最大長(zhǎng)度就是很簡(jiǎn)單的事情，但是如果要求出最長(zhǎng)公共子序列呢？
　　如果需要求出最長(zhǎng)公共子序列的內(nèi)容，需要在填寫矩陣的過(guò)程這個(gè)中記錄當(dāng)前單元格的數(shù)字來(lái)自哪個(gè)地方，分別用左上，向左，向上的箭頭表示，矩陣填寫完之后，通過(guò)回溯，找出對(duì)角線上最長(zhǎng)的箭頭連線，回溯過(guò)程中箭頭的優(yōu)先級(jí)需要一致。
　　發(fā)現(xiàn)下面一篇blog講解的十分詳細(xì)，給出鏈接http://www.cnblogs.com/zhangchaoyang/articles/2012070.html。
　　另一篇也不錯(cuò)，http://blog.csdn.net/yysdsyl/article/details/4226630

　　Google Code Jam 2012 Round 1C
　　Problem C. Box Factory
　　http://code.google.com/codejam/contest/1781488/dashboard#s=p2&a=2
　　這是Google編程挑戰(zhàn)賽2012年第一輪C回的第三道題，盒子工廠。題目意思是有兩條生產(chǎn)線A和B，分別生產(chǎn)盒子和玩具。現(xiàn)在給出兩條生產(chǎn)線上產(chǎn)品的數(shù)量和類型，如果兩條生產(chǎn)線上的產(chǎn)品類型一致，那么把玩具放入盒子，如果不一致，你就要求選擇是把盒子還是把玩具扔掉，然后繼續(xù)匹配裝箱。要求給出一種方案，使得最后得到的產(chǎn)品最多。并且只要求給出最多的這個(gè)數(shù)，不要求具體的方案。
　　這道題與最長(zhǎng)公共子序列類似，下面分析它的解法。
　　f(x,y)表示兩條生產(chǎn)線上前x個(gè)盒子和前y個(gè)玩具得到的最大的產(chǎn)品數(shù)，遞推關(guān)系如下，
　　　　　　x-1 　　　　 　　 x
y-1 　　　　?f(x-1,y-1) 　　 f(x,y-1)
y 　　　　　?f(x-1,y) 　　　?if x.type=y.type, 　　f(x,y)=f(x-1,y-1)+min(x.num,y.num)
　　　　　　　　　　　　　 ?else, 　　　　　　　 ?f(x,y)=max(f(x-1,y),f(x,y-1))
　　代碼如下，

# BoxFactory.pyimport sysdef ReadInt(fin):return int(fin.readline().rstrip("\n"))def ReadInts(fin):return list(int(v) for v in fin.readline().rstrip("\n").split())def BoxFactory(na,nb,A,B):L = [[0 for j in range(nb+1)] for i in range(na+1)]for i in range(1,na+1):for j in range(1,nb+1):if A[2*i-1]==B[2*j-1]:L[i][j] = L[i-1][j-1] + min(A[2*i-2],B[2*j-2])else:L[i][j] = max(L[i-1][j],L[i][j-1])return L[na][nb]fname = "" if len(sys.argv)<2:fname = raw_input("please input the test input:") else:fname = sys.argv[1]fin = open(fname) fout = open("result.txt","w") caseNum = ReadInt(fin) for case in range(caseNum):(na,nb) = ReadInts(fin)A = ReadInts(fin)B = ReadInts(fin)r = BoxFactory(na,nb,A,B)answer = "Case %d: %d\n" %(case+1,r)fout.write(answer)fin.close() fout.close()

　　這是沒有做任何修改的LCS的過(guò)程，但是測(cè)試結(jié)果中存在一些問題，頁(yè)面給出的示例的第二個(gè)結(jié)果就不對(duì)，需要繼續(xù)改進(jìn)。

轉(zhuǎn)載于:https://www.cnblogs.com/Frandy/archive/2012/06/16/algorithm_course_7_1.html

總結(jié)

以上是生活随笔為你收集整理的Algorithm Course Review(7.1)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。