動態(tài)規(guī)劃策略教材-免費閱讀
【正文】 :51:2619:51:26March 23, 2023 1意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 3月 下午 7時 51分 :51March 23, 2023 1少年十五二十時，步行奪得胡馬騎。 2023年 3月 23日星期四 7時 51分 26秒 19:51:2623 March 2023 1做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點的射線向前。 問題：給定序列 A，求其最長的子序列 例如（ 5,2,8,6,3,6,9,7）的最長子序列是(2,3,6,7) kiii aaa ??? ?21 ),( 21 kiii aaa ?分析： 構(gòu)造兩個實例 ① （ 5,2,8,6,3,6,9,7） ② （ 3,18,7,14,10,12,23,41,16,24） 2 5 3 6 8 6 7 9 有什么規(guī)律嗎？ 3 7 18 10 14 12 16 23 24 41 ② （ 3,18,7,14,10,12,23,41,16,24） 3 7 18 10 14 12 23 16 41 24 構(gòu)造兩個實例 ① （ 5,2,8,6,3,6,9,7） ② （ 3,18,7,14,10,12,23,41,16,24） for j = 1 to n L(j) = 1+max{L(i) | (i,j)∈ E｝ end for return max{L(j)|j=1,2,… n} There is one last issue to be cleared up: the Lvalues only tell us the length of the optimal subsequence, so how do we recover the subsequence itself? This is easily managed with a bookkeeping device. While puting L(j), we should also note down prev(j), the nexttolast node on the longest path to j. The optimal subsequence can then be reconstructed by following these backpointers. 靜夜四無鄰，荒居舊業(yè)貧。 ?由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關系 。 ? 例， 序列 Z={B， C， D， B}是序列 X={A， B， C， B， D，A， B}的子序列，相應的遞增下標序列為 {2， 3， 5， 7}。 )/4()(11)()(1)( 2/311nnPnnknPkPnPnnk???????????? ????算法復雜度分析 ： ?對于 n個矩陣的連乘積，設其不同的計算次序為 P(n)。i=1。 貪心法？ 窮舉法？ F1() F3() F4() F5() F2() 用函數(shù) fi(x)表示第 i層節(jié)點到底部（假設是第 N層）的路徑上數(shù)字和的最大值。否則（ 1， 3， 5， 7）也不可能是優(yōu)化的。 實際編程時，還缺少一個東西？每個項目到底分配到多少資源量？ 定義數(shù)組 a[i][j] a[i][j]=kmax 表示前 i個項目分配資源量為 j的情況下，使得前 i個項目利潤最時，第 i個項目分配的資源量為 kmax。這種計算次序可以用加括號的方式來確定。算法所占用的空間顯然為 O(n2)。 (3)若 xi≠yj且 zk≠yj， 則 Zk是 Xi和 Yj1的最長公共子序列。 ?其他 情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關系如下： ?????????????????jijiyxjiyxjijijicjicjicjic。 :51:2619:51:26March 23, 2023 1他鄉(xiāng)生白發(fā)，舊國見青山。 19:51:2619:51:2619:51Thursday, March 23, 2023 1不知香積寺，數(shù)里入云峰。 :51:2619:51Mar2323Mar23 1越是無能的人，越喜歡挑剔別人的錯兒。 2023年 3月 23日星期四 7時 51分 26秒 19:51:2623 March 2023 1一個人即使已登上頂峰，也仍要自強不息。 , March 23, 2023 閱讀一切好書如同和過去最杰出的人談話。 19:51:2619:51:2619:513/23/2023 7:51:26 PM 1成功就是日復一日那一點點小小努力的積累。 :51:2619:51Mar2323Mar23 1故人江海別，幾度隔山川。當 i=0或 j=0時，空序列是Xi和 Yj的最長公共子序列 。 分析：設 X=“ abcbdab” Y=“ bdcdb” 最長公共子序列是： Z=“ bcdb” ① 子問題劃分及依賴關系 子問題邊界： X和 Y 起始位置為 1， X的終止位置是 i， Y 的 終止位置是 j，記作 Xi=x1,x2,…, xi， Yj=y1,y2,…, yj 依賴關系：
規(guī)章制度相關推薦
鄂ICP備17016276號-1