動(dòng)態(tài)規(guī)劃算法實(shí)驗(yàn)報(bào)告-資料下載頁(yè)
2025-07-22 00:25本頁(yè)面
【正文】 ) m[i][j] = max(m[i+1][j],m[i+1][jw[i]]+v[i])。 } m[1][c]=m[2][c]。 if(c=w[1]) m[1][c]=max(m[1][c],m[2][cw[1]]+v[1])。}//找出最優(yōu)解，0表示不能裝，1表示能裝void traceback(int **m,int n,int c,int *x,int *w){ for(int i=1。in。i++) { if(m[i][c]==m[i+1][c]) x[i]=0。 else { x[i]=1。 c=w[i]。 } } x[n]=(m[n][c]==0)?0:1。}int main(){ int *v=new int[N+1]。 int *w=new int[N+1]。 int **m=new int* [N+1]。 int *x=new int [N+1]。 for(int i=0。iN+1。i++) { m[i]=new int[C+1]。 } cout輸入重量序列,N個(gè)endl。 for(int i=1。i=N。i++) cinw[i]。 cout輸入價(jià)值序列,N個(gè)endl。 for(int i=1。i=N。i++) cinv[i]。 knapsack(m,N,C,w,v)。 traceback(m,N,C,x,w)。cout最優(yōu)值：m[1][C]endl。cout是否裝入背包的情況：。 for(int i=1。i=N。i++) { coutx[i]。 } for(int i=0。iN+1。i++) { delete m[i]。 } delete []m。 return 0。}運(yùn)行結(jié)果 最優(yōu)二叉搜索樹(shù)includeiostreamincludecmathincludelimitsdefine N 100using namespace std。const double MAX = numeric_limitsdouble::max()。 //double的最大值//a[i]為結(jié)點(diǎn)i被訪(fǎng)問(wèn)的概率//b[i]為“虛結(jié)點(diǎn)”i被訪(fǎng)問(wèn)的概率//m[i][j]用來(lái)存放子樹(shù)（i，j）的期望代價(jià)//w[i][j]用來(lái)存放子樹(shù)（i，j）的所有結(jié)點(diǎn)（包括虛結(jié)點(diǎn)）的a,b概率之和//s[i][j]用來(lái)跟蹤root的void OptimalBinarySearchTree(double *a,double *b,int n){ int s[N][N]。 double m[N][N]。 double w[N][N]。 int i,j,l,r。 for(i=1。 i=n+1。 i++) { m[i][i1] = b[i1]。 w[i][i1] = b[i1]。 } for(l=1。 l=n。 l++) { for(i=1。 i=nl+1。 i++) { j = l+i1。 m[i][j] = MAX。 w[i][j] = w[i][j1] + a[j] +b[j]。 for(r=i。 r=j。 r++) { double k = m[i][r1] + w[i][j] + m[r+1][j]。 if(km[i][j]) { m[i][j] = k。 s[i][j] = k。 } } } } coutm[1][n]。}int main(){ double a[N],b[N]。 int n。 double sum = 0。 int i,j,l。 cout請(qǐng)輸入關(guān)鍵字的個(gè)數(shù)：endl。 cinn。 cout請(qǐng)輸入每個(gè)關(guān)鍵字的概率：endl。 for(i=1。 i=n。 i++) { cina[i]。 sum += a[i]。 } cout請(qǐng)輸入每個(gè)虛擬鍵的概率：endl。 for(i=0。 i=n。 i++) { cinb[i]。 sum += b[i]。 } if(abs(sum1)) { cout輸入的概率和不為1,請(qǐng)重新輸入endl。 } cout最優(yōu)二叉查找樹(shù)的期望搜索代價(jià)為：。 OptimalBinarySearchTree(a,b,n)。 return 0。}運(yùn)行結(jié)果：實(shí)驗(yàn)總結(jié) 通過(guò)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的這個(gè)題目，對(duì)動(dòng)態(tài)規(guī)劃算法有了進(jìn)一步的了解。先分析問(wèn)題，判斷是否具有最優(yōu)子結(jié)果和重疊字問(wèn)題的性質(zhì)。
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1