【正文】 上節(jié) 下節(jié) 算法 main（） { int a,b,c。j++) if (a[j]a[s1]) { s2=s1。j++) { if (a[j]a[s1]) { s2=s1。 b[j]=a[j]。這是一道兩次運用貪心策略解決的問題 。 data[i]=j。 if(slen) {print(“data error”)。 and length(n) 1) delete(n,1,1)。i=s 。 此方式同樣存在操作比較復(fù)雜的問題 。 上節(jié) 下節(jié) 可絕對貪婪問題 問題分析 在位數(shù)固定的前提下 ， 讓高位的數(shù)字盡量小其值就較小 ， 依據(jù)此貪婪策略就可以解決這個問題 。編程對給定的 N和 S， 尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小 。這樣可能會有比較多字符移動操作，算法效率不高。 len=length(n)。i=i+1) { j=leni+1。 算法 2如下： Delete_digit（ ） {char n[100]。 j=j1。 【 例 2】 數(shù)列極差問題 在黑板上寫了 N個正整數(shù)作成的一個數(shù)列 ， 進行如下操作 :每一次擦去其中的兩個數(shù) a和 b， 然后在數(shù)列中加入一個數(shù) a b+1， 如此下去直至黑板上剩下一個數(shù) ， 在所有按這種操作方式最后得到的數(shù)中 ， 最大的記作 max， 最小的記作 min，則該數(shù)列的極差定義為 M=maxmin。 input(n)。 s2=2。 s2=2。 上節(jié) 下節(jié) 數(shù)學(xué)模型 記真分?jǐn)?shù) F=A/B；對 B/A進行整除運算 ,商為 D, 余數(shù)為 0＜ K＜ A，它們之間的關(guān)系及導(dǎo)出關(guān)系如下： B=A*D+K， B/A=D+K/A＜ D+1， A/B＞ 1/(D+1)， 記 C=D+1。} if( a 1) print(+)。i++) { input(GZ)。 請編寫算法 ， 讓先取數(shù)者勝 ， 模擬取數(shù)過程 。這樣可以保證我們自始自終取到偶編號的數(shù)，而計算機自始自終取到奇編號的數(shù)。 一般情況下通過一些實際的數(shù)據(jù)例子 (當(dāng)然要有一定的普遍性 ),就能從直觀上就能判斷一個問題是否可以用貪婪算法 ， 如本節(jié)的例 2。以圖 411為例就是如此。)。max=?,a[1][1][2])。 上節(jié) 下節(jié) 3. 設(shè)計動態(tài)規(guī)劃算法的基本步驟 設(shè)計一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃算法的步驟： 1) 劃分階段 2) 選擇狀態(tài) 3) 確定決策并寫出狀態(tài)轉(zhuǎn)移方程 但是 ,實際應(yīng)用當(dāng)中的簡化步驟： 1) 分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。j=j+1) if(t= xi[ji]) break。 input (m)。 input(q[j])。} for(i=1。 input (n)。} u= course(i,i) + course(i+1,j)+ r[i]*r[i+1]*r[j+1]。 for (i=1。 if(i=j1) { [i][i+1]=i。 for (i=1。 s=n1。j=n。所以，我們只能用動態(tài)規(guī)劃的方法去解決 。 //構(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。 【 例 5】 最長不降子序列 。 for (i=1。 \s=0\ m[i][i+1]= r[i]*r[i+1]*r[i+2]。 } 上節(jié) 下節(jié) 算法 3(非遞歸算法 ) main（ ） { int n,r[100],m[100][100],[100][100]。j=n。 print(“How size every matrixe?”)。 } } 上節(jié) 下節(jié) int course(int i, int j) { int u,t。 用二維矩陣 ij(n*n)來存儲使 mij為最小值時的 k 值。 for(i=m。k=m。 上節(jié) 下節(jié) 對于一般問題設(shè)計 算法 如下 ： main( ) { int i,j,k,m,n,rest。i= n1。 3) 有 重疊子問題 。 a[i][j][3]=0。 a[50][50][1]代替數(shù)組 data， a[50][50][2]代替數(shù)組 d, a[50][50][3]記錄解路徑。 所以 ， 這種多階段決策最優(yōu)化的解決問題的過程稱為 動態(tài)規(guī)劃 。 ： 從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo) ， 每一步都作一個不可回溯的決策 ,盡可能地求得最好的解 。（如果奇編號數(shù)之和與偶編號數(shù)之和同樣大，我們第一次可以任意取數(shù)，因為當(dāng)兩者所取數(shù)和相同時，先取者為勝。 假若 ,某國的幣種是這樣的 ,共 9種 :100,70,50,20,10,7,5,2,1。 上節(jié) 下節(jié) 算法 main( ) { int i,j,n,GZ,A； int B[8]={0,100,50,20,10,5,2,1},S[8]。 else 上節(jié) 下節(jié) while(a1) { c = b \ a + 1 a = a * c b: b = b * c print( 1/,c)。 如：7/8=1/2+1/3+1/24。 n=n1。 n=n1。 2) 求最大和最小的兩個數(shù)的函數(shù)至少要返回兩個數(shù)據(jù) ， 為方便起見我們用全局變量實現(xiàn) 。i=i+1) print(data[i],39。 if (jj1) data[i]=j+i。 } 算法說明 1： 注意記錄刪除位置不一定是要刪除數(shù)字 d的下標(biāo)，因為有可能 d的前或后有可能已經(jīng)有字符被刪除， d的前面已經(jīng)有元素刪除容易想到，但一定不要忽略了其后也有可能已刪除了字符，實例 2中刪除 1時，其后的 2已被刪除。 break。} Delete_digit（ ） {char n[100]。特別地還要考慮若結(jié)果串是“ 0000”時，不能將全部 “ 0”都刪除，而要保留一個 “ 0”最后輸出。 貪婪算法 沒有固定的算法框架 ， 算法設(shè)計的關(guān)鍵是貪婪策略的選擇 。 再看以下兩個實例又可總結(jié)出一些需要算法特殊處理的情況 。 for(i=b。 if (jj1) data[i]=j+i。i=i+1) print(data[i],39。 j1=0。 print(n)。 所以不但要選取最大和最小 ， 還必須記錄它們的位置 ， 以便將其覆蓋 。 while (n2) { max2(a,n)。 while (n2) { min2(a,n)。 由于計算最大結(jié)果和計算最小結(jié)果需要獨立進行 ,所以算法的空間復(fù)雜度為 O(2n)。 input(b)。這樣，七種 幣值就可表示為 B[i],i=1,2,3,4,5,6,7?！?,否則將會重復(fù)計算 。 這是對第一個回合的分析，顯然對以后整個取數(shù)過程都適用。 if(s1s2) print(“first take left”)。 上節(jié) 下節(jié) 在動態(tài)規(guī)劃算法策略中 ， 體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進行決策 , 并通過多階段決策來最終解決問題 。二維數(shù)組 a的存儲內(nèi)容如下： d[n][j]=data[n][j] j=1,2,?? ,n； i=n1,n2,?? 1， j=1,2,?? ,i；時 d[i][j]=max(d[i+1][j]， d[i+1][j+1])+data[i][j] 最后 a[1][1]存儲的就是問題的結(jié)果。i) for (j=1 。 上節(jié) 下節(jié) 動態(tài)規(guī)劃算法的問題及決策應(yīng)該具有三個性質(zhì)：最優(yōu) 化原理、無后向性、子問題重疊性質(zhì)。j=j+1)// f(i)與 i有關(guān)的表達式 xi[j]=j=max(或 min){g(xi1[j1——j2])， ……， g(xi1[jk——jk+1])}； t=g(x1[j1—j2])。 3) 開辟記錄中間結(jié)果的一維數(shù)組數(shù)組 temp， 記錄正在計 算的最大收益 。j= n。j= n。 2） 第二階段 ,計算兩個相鄰矩陣相乘的計算量 , 共 n1組 3） 第三階段 ,計算兩個相鄰矩陣相乘的計算量 , 共 n2組 4） 最后一個階段 ,是 n個相鄰矩陣相乘的計算量 ,共 1組 , 是問題解 。 for (j=1。 matrix2（ ） { int n,。i=n。 [i][j]=k。 for (i=1。 if (t m[i][j]) { m[i][j] = t。 print（ and M,[i][j]+1, “*M”， j ） 。 n=strlen(b), k=lcs_len(n,m)。 else { str[k]= a[i1]。 上節(jié) 下節(jié) 2．存儲、子問題合并 定義 c[i][j]為序列 a0,a1,? ,ai2” 和 “ b0,b1,? ,bj1” 的 最長公共子序列的長度，計算 c[i][j]可遞歸地表述如下： 1） c[i][j]=0 如果 i=0或 j=0； 2） c[i][j]=c[i1][j1]+1 如果 i,j0,且 a[i1]=b[j1]； 3） c[i][j]=max(c[i][j1],c[i1][j]) 如果 i,j0,且 a[i1]≠b[j 1]。 怎么樣更直觀 、 合理地輸出結(jié)合過程 ？ 即算法的輸出能使用戶直接了解計算矩陣的過程 。i++) { j=i+s。 for (i=1。 } int u= course (i,i)+ course (i+1,j)+r[i]*r[i+1]*r[j+1]。 / for (j=1。 k j。i=n+1。 print(f[n])。j= n。 print(“input gain table:”)。 上節(jié) 下節(jié) 突出階段性的動態(tài)規(guī)劃應(yīng)用 【 例 2】 資源分配問題 。 上節(jié) 下節(jié) 4. 標(biāo)準(zhǔn)動態(tài)規(guī)劃的基本框架 for( j=1 。i= n1。i=n。 在知道數(shù)塔的全貌的前提下，可以用 枚舉法 或下一章將學(xué)習(xí)的搜索算法來完成。 利用可行的決策 ， 求出可行解的一個解元素 。 s1=0； s