第7章，動態規劃，Dynamic Programming
　　又是動態規劃，上一次想整理動態規劃，結果還沒有整理完，實際上是沒有整理的動力了，整理一道題都好費時間的。
　　現在又要整理，這次能整理多少了？已經開始寫了，那至少有些成果吧。

　　最長公共子序列問題
　　書上例題，先簡單分析一下，然后看與之類似的一個問題。
　　給出兩個長度為n和m的字符串A=a1a2..an和B=b1b2..bm，確定A和B的最長公共子序列的長度。其中，子序列的定義是形式為ai1,ai2,..aik的字符串，ij滿足1<i1<i2<..<ik<n，也就是沒有要求子序列是元字符串中連續的字符序列。
　　為了使用動態規劃技術，就需要找到最長公共子序列長度的遞推公式。令L(i,j)表示A的前i個字符和B的前j個字符中最大公共子序列長度，如果i或j為0，那么L(i,j)=0，這是初始條件。當ai=bj時，最長公共子序列長度應該增加1，當ai!=bj時呢？
　　　　　　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))
　　這就是動態規劃二維矩陣的遞推關系。有了這個之后，求出最大長度就是很簡單的事情，但是如果要求出最長公共子序列呢？
　　如果需要求出最長公共子序列的內容，需要在填寫矩陣的過程這個中記錄當前單元格的數字來自哪個地方，分別用左上，向左，向上的箭頭表示，矩陣填寫完之后，通過回溯，找出對角線上最長的箭頭連線，回溯過程中箭頭的優先級需要一致。
　　發現下面一篇blog講解的十分詳細，給出鏈接http://www.cnblogs.com/zhangchaoyang/articles/2012070.html。
　　另一篇也不錯，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編程挑戰賽2012年第一輪C回的第三道題，盒子工廠。題目意思是有兩條生產線A和B，分別生產盒子和玩具。現在給出兩條生產線上產品的數量和類型，如果兩條生產線上的產品類型一致，那么把玩具放入盒子，如果不一致，你就要求選擇是把盒子還是把玩具扔掉，然后繼續匹配裝箱。要求給出一種方案，使得最后得到的產品最多。并且只要求給出最多的這個數，不要求具體的方案。
　　這道題與最長公共子序列類似，下面分析它的解法。
　　f(x,y)表示兩條生產線上前x個盒子和前y個玩具得到的最大的產品數，遞推關系如下，
　　　　　　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的過程，但是測試結果中存在一些問題，頁面給出的示例的第二個結果就不對，需要繼續改進。

轉載于:https://www.cnblogs.com/Frandy/archive/2012/06/16/algorithm_course_7_1.html

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。