動態(tài)規(guī)劃ppt課件-資料下載頁
2024-11-03 18:12本頁面
【正文】 ool job。 }。 Jobtype *d=new Jobtype[n]。 for(int i=0。 in。 i++){ d[i].key = a[i]b[i]?b[i]:a[i]。 d[i].job = a[i]=b[i]。 d[i].index = i。 } sort(d,n)。 0 1 2 3 4 5 A 2 5 7 10 5 2 B 3 8 4 11 3 4 key 2 5 4 10 3 2 job T T F T F T index 0 1 2 3 4 5 56 int j=0, k=n1。 for(int i=0。 in。 i++){ if(d[i].job) c[j++] = d[i].index。 else c[k ] = d[i].index。 } j = a[c[0]]。 k = j+b[c[0]]。 for(int i=1。 in。 i++){ j += a[c[i]]。 k = jk ? k+b[c[i]] : j+b[c[i]]。 } delete d。 return k。 //最優(yōu)加工時間 } 0 1 2 3 4 5 A 2 5 7 10 5 2 B 3 8 4 11 3 4 排序之后 : key 2 2 3 4 5 10 job T T F F T T index 0 5 4 2 1 3 C 0 5 1 3 2 4 j 2 4 9 19 26 31 k 5 9 17 30 34 37 j k 57 給定 n種物品和一背包。物品 i的 重量是 wi，其 價值為 vi，背包的容量為 C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的 總價值最大 ? 01背包問題是一個特殊的整數(shù)規(guī)劃問題。 nixxv iniii ?????1},1,0{ ,ma x1nixCxw iniii ??????1},1,0{ ,101背包問題 C=6 1 2 3 wi 2 3 4 vi 1 2 5 xi 1 0 1 58 設(shè)所給 01背包問題的子問題 (遞歸關(guān)系 ) 的最優(yōu)值為 m(i， j)， 即 m(i， j)是背包容量為 j，可選擇物品為 i， i+1， … ， n時 01背包問題的最優(yōu)值。 ??nikkk xvm a x???????????nkixjxwknikkk},1,0{01背包問題 i i+1 i+2 …… n 最優(yōu)值 : m(i, j) 背包容量 : jwi, j(wi未裝入 ) 背包容量為 j 59 由 01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，建立計(jì)算 m(i， j)的遞歸式如下 : iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x{),(nnnwjwjvjnm???????00),(01背包問題 1 2 … i i+1 … n w1 w2 wi wi+1 wn v1 v2 vi vi+1 vn m(i,j) m(i+1,j) m(n,j) 背包容量 : j 1. 0≤jwi。 2. j≥wi Wij,無法裝入 60 01背包問題實(shí)例分析 C=6 1 2 3 wi 2 3 4 vi 1 2 5 xi 1 0 1 0 1 2 3 4 5 6 1 0 0 0 0 0 0 6 2 0 0 0 2 5 5 5 3 0 0 0 0 5 5 5 j i iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x{),(nnnwjwjvjnm???????00),(m[2][3]=max(m[3][3],m[3][0]+2)=2。 m[2][4]=max(m[3][4],m[3][1]+2)=5。 m[2][5]=max(m[3][5],m[3][2]+2)=5。 m[2][6]=max(m[3][6],m[3][3]+2)=5。 m[1][6]=max(m[2][6],m[2][4]+1)=6。 c n 61 由 01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，建立計(jì)算 m(i， j)的遞歸式如下 : 算法復(fù)雜度分析： 從 m(i， j)的遞歸式容易看出，算法需要 O(nc)計(jì)算時間。當(dāng)背包容量 c很大時，算法需要的計(jì)算時間較多。例如，當(dāng) c2n時，算法需要 Ω(n2 n)計(jì)算時間。 iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x{),(nnnwjwjvjnm???????00),(01背包問題 62 代碼分析 define NUM 100 void knapsack(int v[ ], int w[ ], int c, int n, int m[ ][NUM]) { int jMax=min(w[n]1,c)。 for( int j=0。 j=jMax。 j++) m[n][j]=0。 for( int j=w[n]。 j=c。 j++) m[n][j]=v[n]。 for( int i=n1。 i1。 i) { jMax=min(w[i]1,c)。 for( int j=0。 j=jMax。 j++) m[i][j]=m[i+1][j]。 for(int j=w[i]。 j=c。 j++) 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])。 } nnnwjwjvjnm???????00),(iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x{),(63 代碼分析 void traceback( int m[ ][NUM], int w[ ], int c, int n, int x[ ]) { 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)? 1:0。 } C=6 1 2 3 wi 2 3 4 vi 1 2 5 xi 1 0 1 0 1 2 3 4 5 6 1 0 0 0 0 0 0 6 2 0 0 0 2 5 5 5 3 0 0 0 0 5 5 5 i c
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1