【文章內(nèi)容簡(jiǎn)介】 公共子序列。 即，原問題最優(yōu)解，包含子問題最優(yōu)解； 因此，最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 ②寫出遞歸方程 ③循環(huán)實(shí)現(xiàn)，計(jì)算最優(yōu)值C[ i][ j]，算法描述Int lcsLength( x[ ], y[ ], b[ ][ ]){ int m=。 n=。 for(int i=1。 im。i++) C[i][0]=0。 //y序列空 for(int i=1。 in。i++) C[0][i]=0。 //x序列空 for (int i = 1。 i = m。 i++) //x序列長(zhǎng)為ｍ for (int j = 1。 j = n。 j++)　　 //ｙ序列長(zhǎng)為n if (x[i]==y[j]) { C[i][j]=C[i1][j1]+1。 b[i][j]=1。} else if (c[i1][j]=c[i][j1]) { C[i][j]=C[i1][j]。 b[i][j]=2。} else { C[i][j]=C[i][j1]。 b[i][j]=3。}return C[m][n]。}u 時(shí)間復(fù)雜度分析：該算法時(shí)間復(fù)雜度：O(m*n)④構(gòu)造最長(zhǎng)公共子序列，算法描述：void LCS (char X[ i], Y[ j], int b[ ][ ]){ if (i ==0 || j==0) return。 if (b[ i][ j]== 1) { LCS( X[ i1], Y[ j1], b)。 ( x[ i] )。 } else if (b[ i][ j]== 2) LCS(X[i1]，Y[ j]，b)。 else if (b[ i][ j]== 3) LCS(X[ i] ，Y[j1], b)。}u 時(shí)間復(fù)雜度分析：　此算法每一次遞歸調(diào)用使得i或j減１，因此該算法時(shí)間復(fù)雜度為O(m+n)３、長(zhǎng)江游艇俱樂部在長(zhǎng)江上設(shè)置了n個(gè)游艇出租站1,2…n.游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i，j)，其中1=ij=n；試設(shè)計(jì)一個(gè)算法，計(jì)算出游艇從出租站1到出租站n所需最少租金？（見習(xí)題集第三章算法設(shè)計(jì)與計(jì)算題T2）掌握動(dòng)態(tài)規(guī)劃方法求解０－１背包問題？ 答：①分析問題的最優(yōu)解結(jié)構(gòu) 設(shè)（y1,y2,…yn）所給0－1背包容量為M的解； 則，（y2,…yn）相應(yīng)子問題背包容量為M－w1的解； （即原問題最優(yōu)解，包含了子問題最優(yōu)解） ②遞歸定義最優(yōu)值③計(jì)算最優(yōu)值m(i，j) void knapsack( int v[ ], int w[ ], int M, int m[ ] [ ] ){int n=。 if ( Mw[ n] )　　　 // i=n時(shí)，只有１個(gè)物品　 m[ n][ M]=0。 else if (M=w[ n]) { m[ n][ M]=v[ n]。 M=Mw[ n]。 } for( int i=n1。 i=1。 i) // in時(shí)，xi…xn多個(gè)物品 { if (Mw[ i]) m[ i] [M]=m[ i+1][ M]。 else if (M=w[ n]) { m[ i][ M]=( m[ i+1][ M], m[ i+1][Mw[ i]+v[i])。 M=Mw[ i]。 } }}u 該算法時(shí)間復(fù)雜度：O(c*n) 　　 c常數(shù)④構(gòu)造最優(yōu)解void trackack( int m[ ] [ ], int w[ ], int M, int x[ ] ){//x[ i]標(biāo)記i是否放入背包 int n=。 for( int i=1。 in。 i++ ) //判斷前n1個(gè)物體是否放入背包 { if (m[ i][ M]=m[ i+1][ M] ) x[ i]=0。 else { x[ i]=1。 M=Mw[ i]。 } } x[ n]=(m[ n][ M]0)? 1:0 。 //判斷第n個(gè)物體是否放入背包 }u 該算法時(shí)間復(fù)雜度：O(n) 　　 第 4 章 貪心算法 貪心算法基本思想？答：從問題的初始解出發(fā)逐步逼近給定的目標(biāo)，每一步都做出當(dāng)前看來是最優(yōu)的選擇（貪心選擇），最終得到整個(gè)問題的最優(yōu)解 貪心算法的基本要素？答：貪心選擇性； 最優(yōu)子結(jié)構(gòu) 貪心算法與動(dòng)態(tài)規(guī)劃算法的異同?答：1 ） 相同點(diǎn)：　對(duì)于要求解的問題都具有最優(yōu)子結(jié)構(gòu)；2 ）不同點(diǎn)： 算法的基本思想不同；　　 求解問題的類型不同；　　　　例：普通背包問題　　貪心算法求解　　　　　　01背包問題　　動(dòng)態(tài)規(guī)劃算法求解設(shè)計(jì)普通背包裝載問題的貪心算法? 并分析其時(shí)間復(fù)雜度？答：float greedy_knapsack ( float M, float w[ ], float p[ ], float x[ ] ) // M 背包載重 x[ ]背包問題最優(yōu)解, w[ ]物品重量， P[ ]物品價(jià)值{ int n=。 //n物品的個(gè)數(shù) float pp=0。 //pp計(jì)算當(dāng)前背包總價(jià)值 float mm＝M。 //mm背包剩余載重for( int i=1。i=n。 i++ ){ float ww[ i]= p[ i] / w[ i]； //計(jì)算物品單位價(jià)值ww[ ] x[ i]=0。 } //初始化，所有物品沒有放入背包Mergesort (w[ i ], ww[ i]，n )。 //按單位價(jià)值將物品排序，便于貪心選擇for( int i=1。 i=n。 i++ ) //貪心選擇，總是選擇價(jià)值最大放入背包 { if ( w[ i]=mm ) //當(dāng)前物品小于背包剩余載重 { x[ i]=1。 mm=mm w[ i]。 pp=pp + p[ i]。 } //整個(gè)放入背包 else { x[ i]=mm/w[ i]。 pp=pp + x[ i]*p[ i]。 break。 } //i部分放入背包 }return pp。}該算法主要包括以下幾部分：216。 計(jì)算物品單位價(jià)值時(shí)間，其時(shí)間復(fù)雜度O(n)； 216。 按照物品單位價(jià)值排序時(shí)間，其時(shí)間復(fù)雜度為O(n*logn)?！　　?合并排序時(shí)間)216。 貪心選擇時(shí)間，其時(shí)間復(fù)雜度為O(n)； 故該算法的時(shí)間復(fù)雜度為：O(n*logn+2n)； 記為： O(n*logn)設(shè)計(jì)找零問題的貪心算法? 并分析其時(shí)間復(fù)雜度？答：void greedy_zhaoling ( float GZ, int B[ ], int S[ ] )　 //GZ應(yīng)發(fā)工資 { B[ j]初始化排序；　　//為了貪心選擇，依次選最大幣種 for( j=1, j=6。j++) { S[ j]=0； //初始化S[ j]　　 A=GZ/B[ j]。 //A表示對(duì)應(yīng)j幣種張數(shù) S[ j]=A。 //S[ j]存放對(duì)應(yīng)j幣種總張數(shù) GZ=GZA*B[ j]。 } //每求出一種面額所需的張數(shù)后， 一定要把這部分金額減去： for(i=1。i=6。i++) print( B[ i], “”, S[ i])。 //輸出幣種和對(duì)應(yīng)張數(shù) }設(shè)計(jì)活動(dòng)安排問題的貪心算法? 并分析其時(shí)間復(fù)雜度？答：偽代碼：Int greedyselector(int s[ ], int f[ ], boolean a[ ]){int n=。 //n活動(dòng)的個(gè)數(shù) ；a[ ]按活動(dòng)結(jié)束時(shí)間遞增排序；//便于貪心選擇a[1]=true。 //活動(dòng)１被選中int j=1。 //j記錄最近加入活動(dòng)集合A的活動(dòng)j int count=1。 //count存儲(chǔ)相容活動(dòng)個(gè)數(shù)for(int i=2。 i=n。 i++)//貪心選擇從活動(dòng)j=2…n判是否可加入A { if( 活動(dòng)i的開始時(shí)間，大于　最近活動(dòng)j的結(jié)束時(shí)間 ) {將活動(dòng)i加入活動(dòng)集合A； 　 j=i。 　　//活動(dòng)i作為最近加入活動(dòng)集合A的最近活動(dòng) count++。 } else 活動(dòng)i不加入活動(dòng)集合A；}return count。}程序設(shè)計(jì)語(yǔ)言：Int greedyselector(int s[ ], int f[ ], boolean a[ ]){ int n=。 //n活動(dòng)的個(gè)數(shù) Mergesort (a[ ],f[ ], n )。 //按活動(dòng)結(jié)束時(shí)間排序，便于貪心選擇 a[1]=true。 //活動(dòng)１被選中int j=1。 //j記錄最近依次加入活動(dòng)集合A的活動(dòng)j int count=1。 //count存儲(chǔ)相容活動(dòng)個(gè)數(shù)for(int i=2。 i=n。 i++) //貪心選擇從活動(dòng)i=2…n判是否可加入A { if( s[ i]=f[ j] ){ a[ i]=true。 //將活動(dòng)i加