【正文】 陣相乘的計(jì)算量 ,共 1組 , 是問題解。 print(f[n])。 } rest=n。j= n。 上節(jié) 下節(jié)for( k=2。 print(“input gain table:”)。 5) 數(shù)組 gain存儲(chǔ)第 i個(gè)工程投資數(shù)的最后結(jié)果。 設(shè)有資源 a,分配給 n個(gè)項(xiàng)目 ,gi(x)為第 i個(gè)項(xiàng)目分得資源 x所得到的利潤。xi[ji])for　　 xi[j]=max(或 min){g(xi1[j1—— j2])， …… ， //其它 n1個(gè)階段　 上節(jié) 下節(jié)4. 標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃的基本框架for( 2) 無后向性 (無后效性 )。i++) { print(a[i][j][1],‘’)。 a[i][j][3]=0。i++)　　 for j=1 to i do　　 { input(a[i][j][1])。 a[50][50][1]代替數(shù)組 data， a[50][50][2]代替數(shù)組 d, a[50][50][3]記錄解路徑。以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?4階子問題，遞推出第四層與第五層的和為 : 21(2+19),28(18+10),19(9+10),21(5+16)。 上節(jié) 下節(jié) 問題分析算法設(shè)計(jì)算法小結(jié)第 四 章 基本的算法策略 動(dòng)態(tài)規(guī)劃 認(rèn)識動(dòng)態(tài)規(guī)劃 算法框架 突出階段性的動(dòng)態(tài)規(guī)劃應(yīng)用 突出遞推的動(dòng)態(tài)規(guī)劃應(yīng)用 在動(dòng)態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進(jìn)行決策 , 并通過多階段決策來最終解決問題。 【 例 1】 數(shù)塔問題 上節(jié) 下節(jié) 認(rèn)識動(dòng)態(tài)規(guī)劃【 例 1】 數(shù)塔問題 有形如圖 411所示的一個(gè)數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。算法設(shè)計(jì) 動(dòng)態(tài)規(guī)劃設(shè)計(jì)過程如下： ： 第一步對于第五層的數(shù)據(jù)，我們做如下五次決策： 對經(jīng)過第四層 2的路徑選擇第五層的 19， 對經(jīng)過第四層 18的路徑選擇第五層的 10， 對經(jīng)過第四層 9的路徑也選擇第五層的 10， 對經(jīng)過第四層 5的路徑選擇第五層的 16。如圖 和輸出過程如下： 上節(jié) 下節(jié) 輸出 a[1][1]9 b=d[1][1]data[1][1]=599=50數(shù)組 data 數(shù)組 d 9 59 12 15 50 49 10 6 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 圖 412 數(shù)塔及動(dòng)態(tài)規(guī)劃過程數(shù)據(jù) 上節(jié) 下節(jié)為了設(shè)計(jì)簡潔的算法，我們最后用三維數(shù)組a[50][50][3]存儲(chǔ)以上確定的三個(gè)數(shù)組的信息。i=n。j++)　　　 if (a[i+1][j][2]a[i+1][j+1][2]) 　　　　 { a[i][j][2]=a[i][j][2]+a[i+1][j][2]。i= n1。1) 最優(yōu)化原理 (或稱為最佳原則、 最優(yōu)子結(jié)構(gòu) )。 3) 以自底向上的方式或自頂向下的記憶化方法 (備忘錄 法 )計(jì)算出最優(yōu)值 . 4) 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解。i=i+1){t=txi1[ji]。if(t= 上節(jié) 下節(jié) 突出階段性的動(dòng)態(tài)規(guī)劃應(yīng)用【 例 2】 資源分配問題。 4) 開辟二維數(shù)組 a。 input (n)。j++) a[1,j]=j。} for( j=0 。j++) f[j]=temp[j]。i++) print(gain[i],” ”)。算法設(shè)計(jì) 1. 階段劃分 1）初始狀態(tài)為一個(gè)矩陣相乘的計(jì)算量為 0。main（ i++)quantity： ”,forcourse(intu==} 上節(jié) 下節(jié)(n)。print(“How(j=1。m[i][j]=0。(i=1。j++)} 上節(jié) 下節(jié)courseif(i=j)[i][i+1]=i。returnu=[i][j]=ikj。{）matrixes?”)。i++)(i=1。in。i+1。s=n1。for=kj。}}print(i=1。{輸出算法 記 k1=[1][n]， 則最后一次運(yùn)算的結(jié)合過程是 M1*……*Mk1 和 Mk1+1*……* Mn 記 k2=[1][k1]， M1*……*Mk1 的結(jié)合過程是 M1*……*Mk2 和 Mk2+1*……*Mk1 ……print（ M,i 上節(jié) 下節(jié) 突出遞推的動(dòng)態(tài)規(guī)劃應(yīng)用【 例 4】 求兩個(gè) 字符序列 的 最長 公共字符子序 列。 上節(jié) 下節(jié)Num=100char(k,} 上節(jié) 下節(jié)lcs_len(intif） buile_lcscharint(“Enter(j=1。i=strlen(a),)。while請求出一個(gè)數(shù)列的最長不下降序列。 b[i]=1。i=i1)}{max=0。imaxlong=39。(39。print(a[p])。 “ 貪婪算法 ” “ 遞推法 ” “ 遞歸法 ” “ 枚舉法 ” “ 遞歸回朔法 ” “ 分治法 ” “ 動(dòng)態(tài)規(guī)劃法 ” 上節(jié) 下節(jié) 不同算法策略特點(diǎn)小結(jié)特別地，當(dāng)規(guī)模 N=1時(shí)，能直接得解。“遞歸回朔法 ” 類似于枚舉法的思想 ,遞歸回朔法通過遞歸嘗試遍問題各個(gè)可能解的通路，發(fā)現(xiàn)此路不通時(shí)回朔到上一步繼續(xù)嘗試別的通路。因此，可以說 “ 動(dòng)態(tài)規(guī)劃是高效率、高消費(fèi)的算法 ” 。 上節(jié) 下節(jié)2．多階段過程 “ 貪婪算法 ” 、 “ 遞推法 ” 、 “ 遞歸法 ” 和 “ 動(dòng)態(tài)規(guī)劃法 ” 多階段過程就是按一定順序 (從前向后或從后向前等 )一定的策略 , 逐步解決問題的方法。枚舉法算法的實(shí)現(xiàn) 依賴于循環(huán) ,通過循環(huán)嵌套枚舉問題中各種可能的情況 ,如八皇后問題能用八重循環(huán)嵌套枚舉。 “ 貪婪算法 ” 、 “ 分治法 ” 、 “ 動(dòng)態(tài)規(guī)劃法 ” 與 “ 枚舉法 ” 較適合解最優(yōu)化問題。 那些使目標(biāo)函數(shù)取極值的可行解， 稱為 最優(yōu)解 , 這一類需求取最優(yōu)解的問題 , 又可根據(jù)描述約束條件和目標(biāo)函數(shù)的 數(shù)學(xué)模型的特性或求借問題方法的不同進(jìn)行而細(xì)分為 線形規(guī)則 、 整數(shù)規(guī)則 、 非線形規(guī)則 、 動(dòng)態(tài)規(guī)劃 等問題。 動(dòng)態(tài)規(guī)劃相比一般窮舉也存在一定 缺點(diǎn) :空間占據(jù)過多 ,但對于空間需求量不大的題目來說 ,動(dòng)態(tài)規(guī)劃無疑是最佳方法！ 上節(jié) 下節(jié)