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