算法設(shè)計(jì)與分析-第三章-動(dòng)態(tài)規(guī)劃-資料下載頁(yè)
2025-08-04 10:38本頁(yè)面
【正文】 問題 設(shè)所給 01背包問題的子問題 ??nikkk xvm ax???????????nkixjxwknikkk},1,0{的最優(yōu)值為 m(i， j)，即 m(i， j)是背包容量為 j，可選擇物品為 i，i+1， … ， n時(shí) 01背包問題的最優(yōu)值。由 01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i， j)的遞歸式如下。 iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x{),(nnnwjwjvjnm???????00),( 應(yīng)用舉例－ 0/1背包問題 ? 求解： 1 動(dòng)態(tài)規(guī)劃法 //權(quán)為整數(shù)的迭代法 ? 思考：備忘錄法 01背包問題 權(quán)為整數(shù)的迭代法 void KnapSack(int v[ ],int w[ ],int c,int n,int m[ ][ ])//求 m[ ][ ] { int jMax=min(w[n]1,c)。 for (j=0。j=jMax。j++)//m(n,j)=0 0=jw[n] m[n][j]=0。 for (j=w[n]。j=c。j++)//m(n,j)=v[n] j=w[n] m[n][j]=v[n]。 for (i=n1。i1。i) { int jMax=min(w[i]1,c)。 for (j=0。j=jMax。j++)//m(i,j)=m(i+1,j) 0=jw[i] m[i][j]=m[i+1][j]。 for (j=w[i]。j=c。j++)//m(n,j)=v[n] j=w[n] 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[2][c],m[2][cw[1]]+v[1])。 } 01背包問題 權(quán)為整數(shù)的迭代法 void traceback(int m[ ][],int w[],int c,int x[]) {//求 x[] for(i=1。in。i++) if (m[i][c]==m[i+1][c]) x[i]=0。 else {x[i]=1。c=cw[i]。} x[n]=(m[n][c]0 ? 1:0)。 }
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1