第四章5(貪心、動(dòng)態(tài))-文庫吧
2025-07-31 20:32 本頁面
【正文】 3. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)： 1) 開辟一維數(shù)組 q來存儲(chǔ)原始數(shù)據(jù)。 2) 另開辟一維數(shù)組 f存儲(chǔ)當(dāng)前最大收益情況。 3) 開辟記錄中間結(jié)果的一維數(shù)組數(shù)組 temp， 記錄正在計(jì) 算的最大收益。 4) 開辟二維數(shù)組 a。 5) 數(shù)組 gain存儲(chǔ)第 i個(gè)工程投資數(shù)的最后結(jié)果。 上節(jié) 下節(jié)對(duì)于一般問題設(shè)計(jì) 算法 如下 ：main( ) { int i,j,k,m,n,rest。 int a[100][100]， gain[100]。 float q[100],f[100],temp[100]。 print(“How mang item? ”)。 input (m)。 print(“How mang money? ”)。 input (n)。 print(“input gain table:”)。 for( j=0。j= n。j++) { input(q[j])。 f[j]=q[j]。} for( j=0。j= n。j++) a[1,j]=j。 上節(jié) 下節(jié)for( k=2。k=m。k++) { for( j=0。j= n。j++) { temp[j]=q[j]。 input(q[j])。 a[k][j]=0。} for( j=0 。j= n。j++) for( i=0 。i=j。i++) if（ f[ji]+q[i]temp[j]） { temp[j]=f[ji]+q[i]。 a[k,j]=i。 } for(j=0。j= n。j++) f[j]=temp[j]。 } rest=n。 for(i=m。i=1。i) { gain[i]=a[i][rest]。 rest=restgain[i]。} for(i=1。i=m。i++) print(gain[i],” ”)。 print(f[n])。 } 【 例 3】 n個(gè)矩陣連乘的問題 。 問題分析 算法設(shè)計(jì) 算法 1(遞歸算法 ) 算法 1說明 算法 2(遞歸算法 ) 算法 3(非遞歸算法 ) 輸出算法 上節(jié) 下節(jié)問題分析 多個(gè)矩陣連乘 運(yùn)算是滿足結(jié)合律的。例 : M1[5*20] * M2[20*50] * M3[50*1] * M4[1*100]分別按 ((M1*M2)*M3)*M4， M1*(M2*(M3*M4))， (M1*(M2*M3))*M4 的次序相乘 ,各需進(jìn)行 5750, 115000, 1600次乘法。 這個(gè)問題要用 “ 動(dòng)態(tài)規(guī)劃 ” 算法來完成 : 首先 ,從兩個(gè)矩陣相乘的情況開始； 然后 ,嘗試三個(gè)矩陣相乘的情況； …… 最后 ,等到 n個(gè)矩陣相乘所用的最少的乘法次數(shù)及結(jié)合方式。 上節(jié) 下節(jié)算法設(shè)計(jì) 1. 階段劃分 1）初始狀態(tài)為一個(gè)矩陣相乘的計(jì)算量為 0。2）第二階段 ,計(jì)算兩個(gè)相鄰矩陣相乘的計(jì)算量 , 共 n1組3）第三階段 ,計(jì)算兩個(gè)相鄰矩陣相乘的計(jì)算量 , 共 n2組 4）最后一個(gè)階段 ,是 n個(gè)相鄰矩陣相乘的計(jì)算量 ,共 1組 , 是問題解。 上節(jié) 下節(jié)2. 階段決策 一般地，計(jì)算 M1*M2*M3*……* Mn 其中 M1， M2， ……,Mi 分別是 r1*r2， r2*r3， ……, ri*ri+1階矩陣， i=1,2,3,……n 。 設(shè) mi,j是計(jì)算 Mi*Mi+1*… Mj的最少乘法次數(shù) (1≤i≤j≤n), 對(duì) mi,j有公式： 0 當(dāng) i=j時(shí) ri1*ri*ri+1 當(dāng) j=i+1時(shí) min(mi,k+mk+1,j+rirk+1rj+1) i≤k≤j 當(dāng) ij時(shí) 以上動(dòng)態(tài)規(guī)劃方法是按 s=0,1,2,3,.,n1的順序計(jì)算 mi,i+s的。 用二維矩陣 ij(n*n)來存儲(chǔ)使 mij為最小值時(shí)的 k 值。 上節(jié) 下節(jié)算法 1(遞歸算法 )intr[100],[100][100]。main（ ）{intn,i。print(“Howmangmatrixes?”)。input(n)。peint(“Howsizeeverymatrixe?”)。for(i=1。i=n+1。i++)input(r[i])。print(“Theleastcalculatequantity： ”,course(1,n))。for(i=1。i=n。i++){print(“換行符 ”)。for(j=1。j=n。j++)print([i][j])。}} 上節(jié) 下節(jié)intcourse(inti,intj){intu,t。if(i=j)return0。if(i=j1){[i][i+1]=i。return（ r[i]*r[i+1]*r[r+2]） 。}u=course(i,i)+course(i+1,j)+r[i]*r[i+1]*r[j+1]。[i][j]=i。for(intk=i+1。kj。k++){t=course(i,k)+course(k+1,j)+r[i]*r[k+1]*r[j+1]。if(tu){u=t。[i][j]=k。}}returnu。} 上節(jié) 下節(jié)算法 1說明 以上的遞歸算法雖然解決了問題，但效率很低，有 子問題重疊 ， n=4時(shí)的遞歸過程如下圖： 上節(jié) 下節(jié)算法 2(改進(jìn)后遞歸算法 )intm[100][100],[100][100],r[100]。matrix2（ ）{intn,。print(“Howmangmatrixes?”)。input(n)。print(“Howsizeeverymatrixe?”)。for(i=1。i=n+1。i++)input(r[i])。for(i=1。i=n。i++)/初始化化數(shù)組 和 m。 /for(j=1。j=n。j++){[i][j]=0。m[i][j]=0。}course(1,n)；print(“Theleastcalculatequantity： ”m[1][n])。for(i=1。i=n。i++){print(“換行符 ”)。for(j=1。j=n。j++)print([i][j])。}} 上節(jié) 下節(jié)course(inti,intj){if（ m[i][j]0） returnm[i][j]。if(i=j)return0。if(i=j1)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1