【正文】 buile_lcs (k1, i1,j1)。 //構(gòu)造最長公共子序列 { if （ i=0 or j=0 ） return。 } 上節(jié) 下節(jié) lcs_len(int i， j) //計算最優(yōu)值 { if ( i=0 or j=0) c[i][j]=0。 m=strlen(a)。 上節(jié) 下節(jié) 算法 (遞歸形式 ) int Num=100 char a[Num],b[Num],str[Num]。所以，我們只能用動態(tài)規(guī)劃的方法去解決 。 【 例 5】 最長不降子序列 。 print（ M,i ,“*M”， [i][j]） 。 首先看一下 數(shù)組存儲的信息意義 ， 它是一個二維數(shù)組 ， 元素 [i][j]存儲的是 Mi——Mj相乘的組合點 k1， 也就是說： Mi*Mi+1*……*Mj是由 Mi*Mi+1*……Mk和 Mk+1*……Mj 同樣 ， 在數(shù)組 中我們也能找到 Mi——Mk相乘的組合點 k2，Mk+1——Mj相乘的組合點 k3， ……。j=n。 for (i=1。k++) { t=m[i][k]+m[k+1][j]+ r[i]*r[k+1]*r[j+1]。 m[i][j] =m[i][i] +m[i+1][j] + r[i]*r[i+1]*r[j+1]。 s=n1。 \s=0\ m[i][i+1]= r[i]*r[i+1]*r[i+2]。j++) [i][j]=0。i=n。 for (i=1。 } 上節(jié) 下節(jié) 算法 3(非遞歸算法 ) main（ ） { int n,r[100],m[100][100],[100][100]。 if (tu) { u=t 。 [i][j]=i 。 if(i=j1) { [i][i+1]=i。j=n。 for (i=1。j=n。 for (i=1。 print(“How size every matrixe?”)。 } 上節(jié) 下節(jié) 算法 1說明 以上的遞歸算法雖然解決了問題 ， 但效率很低 ， 有 子問題重疊 ， n=4時的遞歸過程如下圖： 上節(jié) 下節(jié) 算法 2(改進后遞歸算法 ) int m[100][100],[100][100],r[100]。 k++) { t = course(i,k) + course(k+1,j)+r[i]*r[k+1]*r[j+1]。} u= course(i,i) + course(i+1,j)+ r[i]*r[i+1]*r[j+1]。 } } 上節(jié) 下節(jié) int course(int i, int j) { int u,t。i++) { print(“換行符” )。i++) input (r[i])。 input (n)。 用二維矩陣 ij(n*n)來存儲使 mij為最小值時的 k 值。 上節(jié) 下節(jié) 算法設計 1. 階段劃分 1） 初始狀態(tài)為一個矩陣相乘的計算量為 0。 } 【 例 3】 n個矩陣連乘的問題 。} for(i=1。 for(i=m。 } for(j=0。j++) for( i=0 。 input(q[j])。k=m。} for( j=0。 for( j=0。 input (m)。 上節(jié) 下節(jié) 對于一般問題設計 算法 如下 ： main( ) { int i,j,k,m,n,rest。 2) 另開辟一維數(shù)組 f存儲當前最大收益情況 。 設有資源 a,分配給 n個項目 ,gi(x)為第 i個項目分得資源 x所得到的利潤 。j=j+1) if(t= xi[ji]) break。i= n1。j=f(i) 。j=m。 上節(jié) 下節(jié) 3. 設計動態(tài)規(guī)劃算法的基本步驟 設計一個標準的動態(tài)規(guī)劃算法的步驟： 1) 劃分階段 2) 選擇狀態(tài) 3) 確定決策并寫出狀態(tài)轉(zhuǎn)移方程 但是 ,實際應用當中的簡化步驟： 1) 分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 3) 有 重疊子問題 。 可以通俗地說動態(tài)規(guī)劃是“ 帶決策的多階段 、 多方位的遞推算法 ” 。i++) { print(a[i][j][1],??)。max=?,a[1][1][2])。 a[i][j][3]=0。 i=1。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é) 下節(jié) 2．存儲、求解： 1) 原始信息存儲 原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個整型 變量 n存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組 data，存儲成如 下的下三角陣 : 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 上節(jié) 下節(jié) 2) 動態(tài)規(guī)劃過程存儲 必需用二維數(shù)組 a存儲各階段的決策結(jié)果。 上節(jié) 下節(jié) 算法設計 動態(tài)規(guī)劃設計過程如下： ： 第一步對于第五層的數(shù)據(jù)，我們做如下五次決策： 對經(jīng)過第四層 2的路徑選擇第五層的 19， 對經(jīng)過第四層 18的路徑選擇第五層的 10， 對經(jīng)過第四層 9的路徑也選擇第五層的 10， 對經(jīng)過第四層 5的路徑選擇第五層的 16。以圖 411為例就是如此。 所以 ， 這種多階段決策最優(yōu)化的解決問題的過程稱為 動態(tài)規(guī)劃 。 因此一定要注意判斷問題是否適合采用貪婪算法策略 ， 找到的解是否一定是問題的最優(yōu)解 。 由所有解元素組合成問題的一個可行解 。 一般情況下通過一些實際的數(shù)據(jù)例子 (當然要有一定的普遍性 ),就能從直觀上就能判斷一個問題是否可以用貪婪算法 ， 如本節(jié)的例 2。 ： 從問題的某一個初始解出發(fā)逐步逼近給定的目標 ， 每一步都作一個不可回溯的決策 ,盡可能地求得最好的解 。 else s1=s1+data。 for(i=1。這樣可以保證我們自始自終取到偶編號的數(shù)，而計算機自始自終取到奇編號的數(shù)。（如果奇編號數(shù)之和與偶編號數(shù)之和同樣大，我們第一次可以任意取數(shù)，因為當兩者所取數(shù)和相同時，先取者為勝。 如果我們第一次取奇編號 （ 編號為 1） 的數(shù) ， 則接著計算機只能取到偶編號 （ 編號為 2或 N） 的數(shù)； 如果我們第一次取偶編號 （ 編號為 N） 的數(shù) ， 則接著計算機只能取到奇編號 （ 編號為 1或 N1） 的數(shù)； 即無論我們第一次是取奇編號的數(shù)還是取偶編號的數(shù) ， 接著計算機只能取到另一種編號 （ 偶編號或奇編號 ） 的數(shù) 。 取數(shù)結(jié)果為： A 16,7,9,11=43 B 27,12,6,2=47 勝 其實 ， 若我們只能看到兩邊的數(shù)據(jù) ， 則此題無論先取還是后取都無必勝的策略 。 請編寫算法 ， 讓先取數(shù)者勝 ， 模擬取數(shù)過程 。 假若 ,某國的幣種是這樣的 ,共 9種 :100,70,50,20,10,7,5,2,1。 } 上節(jié) 下節(jié) 算法說明 每求出一種面額所需的張數(shù)后 ， 一定要把這部分金額減去： “ GZ=GZA*B[j]。 GZ=GZA*B[j]。i++) { input(GZ)。 上節(jié) 下節(jié) 算法 main( ) { int i,j,n,GZ,A； int B[8]={0,100,50,20,10,5,2,1},S[8]。 3) 利用數(shù)組應用技巧 ,將七種幣值存儲在數(shù)組 B。 為了保證不要臨時兌換零錢 , 且取款的張數(shù)最少 ， 取工資前要統(tǒng)計出所有職工的工資所需各種幣值 (100,50,20,10,5,2,1元共七種 )的張數(shù) 。} if( a 1) print(+)。 else 上節(jié) 下節(jié) while(a1) { c = b \ a + 1 a = a * c b: b = b * c print( 1/,c)。 print(“input denominator”)。 3)輸出 1/C； 4)將 A乘以 C減去 B作為新的 A； 5)將 B乘以 C作為新的 B； 6)如果 A大于 1且能整除 B,則最后一個分母為 B/A； 7)如果 A＝ 1,則最后一個分母為 B。 上節(jié) 下節(jié) 數(shù)學模型 記真分數(shù) F=A/B；對 B/A進行整除運算 ,商為 D, 余數(shù)為 0＜ K＜ A，它們之間的關(guān)系及導出關(guān)系如下： B=A*D+K， B/A=D+K/A＜ D+1， A/B＞ 1/(D+1)， 記 C=D+1。 如：7/8=1/2+1/3+1/24。 } 上節(jié) 下節(jié) 算法分析 算法中的主要操作就是比較查找和計算 ， 它們都是線性的 ， 因此算法的時間復雜度為 O(n)。j=n。 s2=2。 n=n1。 } } 上節(jié) 下節(jié) calculatemax(int a[],int n) { int j。j=n。 s2=2。 n=n1。 print(“maxmin=”, maxmin) } calculatemin(int a[],int n) { int j。j=j+1) {input(a[j])。 input(n)。 2) 求最大和最小的兩個數(shù)的函數(shù)至少要返回兩個數(shù)據(jù) ， 為方便起見我們用全局變量實現(xiàn) 。 注意到由于找到的兩個數(shù)將不再參與其后的運算 ， 其中一個自然地是用它們的計算結(jié)果代替 ， 另一個我們用當前的最后一個數(shù)據(jù)覆蓋即可 。 反過來求最小值時 ， 要先選擇較大的數(shù)操作 。 【 例 2】 數(shù)列極差問題 在黑板上寫了 N個正整數(shù)作成的一個數(shù)列 ， 進行如下操作 :每一次擦去其中的兩個數(shù) a和 b， 然后在數(shù)列中加入一