【正文】 那些使目標函數(shù)取極值的可行解， 稱為 最優(yōu)解 , 這一類需求取最優(yōu)解的問題 , 又可根據(jù)描述約束條件和目標函數(shù)的 數(shù)學模型的特性或求借問題方法的不同進行而細分為 線形規(guī)則 、 整數(shù)規(guī)則 、 非線形規(guī)則 、 動態(tài)規(guī)劃 等問題。枚舉法算法的實現(xiàn) 依賴于循環(huán) ,通過循環(huán)嵌套枚舉問題中各種可能的情況 ,如八皇后問題能用八重循環(huán)嵌套枚舉。 上節(jié) 下節(jié)2．多階段過程 “ 貪婪算法 ” 、 “ 遞推法 ” 、 “ 遞歸法 ” 和 “ 動態(tài)規(guī)劃法 ” 多階段過程就是按一定順序 (從前向后或從后向前等 )一定的策略 , 逐步解決問題的方法?！斑f歸回朔法 ” 類似于枚舉法的思想 ,遞歸回朔法通過遞歸嘗試遍問題各個可能解的通路，發(fā)現(xiàn)此路不通時回朔到上一步繼續(xù)嘗試別的通路。 “ 貪婪算法 ” “ 遞推法 ” “ 遞歸法 ” “ 枚舉法 ” “ 遞歸回朔法 ” “ 分治法 ” “ 動態(tài)規(guī)劃法 ” 上節(jié) 下節(jié) 不同算法策略特點小結print(a[p])。(39。max=0。} b[i]=1。請求出一個數(shù)列的最長不下降序列。whilei=strlen(a),(j=1。(“Enter） if} 上節(jié) 下節(jié)lcs_len(int(k, 上節(jié) 下節(jié)輸出算法 記 k1=[1][n]， 則最后一次運算的結合過程是 M1*……*Mk1 和 Mk1+1*……* Mn 記 k2=[1][k1]， M1*……*Mk1 的結合過程是 M1*……*Mk2 和 Mk2+1*……*Mk1 ……{}printkj。=fors=n1。in。(i=1。[i][i+1]=i。} 上節(jié) 下節(jié)coursem[i][j]=0。(j=1。print(“How=course(intfori++)算法設計 1. 階段劃分 1）初始狀態(tài)為一個矩陣相乘的計算量為 0。j++) f[j]=temp[j]。j++) a[1,j]=j。 4) 開辟二維數(shù)組 a。if(t=i=i+1){t=txi1[ji]。1) 最優(yōu)化原理 (或稱為最佳原則、 最優(yōu)子結構 )。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]。為了設計簡潔的算法，我們最后用三維數(shù)組a[50][50][3]存儲以上確定的三個數(shù)組的信息。如圖 和輸出過程如下： 上節(jié) 下節(jié) 輸出 a[1][1]9 b=d[1][1]data[1][1]=599=50算法設計 動態(tài)規(guī)劃設計過程如下： ： 第一步對于第五層的數(shù)據(jù)，我們做如下五次決策： 對經過第四層 2的路徑選擇第五層的 19， 對經過第四層 18的路徑選擇第五層的 10， 對經過第四層 9的路徑也選擇第五層的 10， 對經過第四層 5的路徑選擇第五層的 16。第 四 章 基本的算法策略 動態(tài)規(guī)劃 認識動態(tài)規(guī)劃 算法框架 突出階段性的動態(tài)規(guī)劃應用 突出遞推的動態(tài)規(guī)劃應用 在動態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進行決策 , 并通過多階段決策來最終解決問題。 上節(jié) 下節(jié) a[50][50][1]代替數(shù)組 data， a[50][50][2]代替數(shù)組 d, a[50][50][3]記錄解路徑。 a[i][j][3]=0。 2) 無后向性 (無后效性 )?！　?xi[j]=max(或 min){g(xi1[j1—— j2])， …… ， forxi[ji]) 5) 數(shù)組 gain存儲第 i個工程投資數(shù)的最后結果。 上節(jié) 下節(jié)for( k=2。 } rest=n。2）第二階段 ,計算兩個相鄰矩陣相乘的計算量 , 共 n1組3）第三階段 ,計算兩個相鄰矩陣相乘的計算量 , 共 n2組 4）最后一個階段 ,是 n個相鄰矩陣相乘的計算量 ,共 1組 , 是問題解。(i=1。i,return（ [i][j]j。course(i,k)if{sizej=n。{courseprint([i][j])。(intreturninputi=n。i++)m[i][i]=0。(i=1。i。k++){(“Theif算法設計1．遞推關系分析 設 A=“a0 ， a1， … ， am1” ， B=“b0 ， b1， … ， bn1”， Z=“z0,z1,…,zk1” 為它們的最長公共子序列。{twon,m)。i， j)(ifelsej=m。ifif(k0) 算法設計 算法 (逆推法 ) 上節(jié) 下節(jié) c[i]=0。ifp:=iresult“貪婪算法 ” 這些策略求解的是最簡單的一類問題，或者說是對問題要求最嚴格的算法策略。在下一章中對其應用做詳細介紹。 “ 貪婪算法 ” 每一步根據(jù)策略得到一個結果傳遞到下一步，自頂向下，一步一步地作出貪心選擇。而對于規(guī)模 不固定 的問題就無法用固定重數(shù)的循環(huán)嵌套來枚舉了 ,有的問題可能通過變換枚舉對象也能用循環(huán)嵌套枚舉實現(xiàn) ,但更多的任意指定規(guī)模的問題是靠遞歸回朔法來 “ 枚舉 ” 或 “遍歷 ” 各種可能的情況。 上節(jié) 下節(jié) 上節(jié) 下節(jié)為了衡量可行解的優(yōu)劣，事先也給出了一定的標準 ,這些標準一般以函數(shù)形式給出 , 這些函數(shù)稱為 目標函數(shù) 。 上節(jié) 下節(jié)3．全面逐一嘗試、比較 “ 蠻力法 ” 、 “ 枚舉法 ” 、 “ 遞歸回溯法 ” 動態(tài)規(guī)劃的 實質 是分治思想和解決冗余。 上節(jié) 下節(jié) 上節(jié) 下節(jié) 算法策略間的比較print}p=j。 }} 上節(jié) 下節(jié)【 例 5】 最長不降子序列 設有由 n個不相同的整數(shù)組成的數(shù)列，記為 : a(1)、 a(2)、 …… 、 a(n)且 a(i)a(j) (ij) 若存在 i1i2i3 … ik 且有 a(i1)a(i2) … a(ik)，則稱為長度為 k的不下降序列。k,c[i][j]=c[i1][j]。forprint}） j=0buile_lcs(“Enter所以，我們只能用動態(tài)規(guī)劃的方法去解決 。從數(shù)組信息中找到了大規(guī)模問題與小規(guī)模問題的遞歸關系：(k=i+1。[i][j](i=1。for}{(k+1,j)+r[i]*r[k+1]*r[j+1]。{quantity： ”m[1][n])。fort。tk(i=j)} 上節(jié) 下節(jié)inti=n+1。 上節(jié) 下節(jié)j= n。j= n。 3) 開辟記錄中間結果的一維數(shù)組數(shù)組 temp， 記錄正在計 算的最大收益。n1。i有關的表達式