動態(tài)規(guī)劃ppt課件(參考版)
2024-11-06 18:12本頁面
【正文】 } 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 。 c=w[i]。 i++) if (m[i][c]==m[i+1][c]) x[i]=0。 } 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。 } m[1][c]=m[2][c]。 j=c。 j++) m[i][j]=m[i+1][j]。 for( int j=0。 i1。 j++) m[n][j]=v[n]。 for( int j=w[n]。 j=jMax。 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)。當(dāng)背包容量 c很大時，算法需要的計算時間較多。 m[1][6]=max(m[2][6],m[2][4]+1)=6。 m[2][5]=max(m[3][5],m[3][2]+2)=5。 2. j≥wi Wij,無法裝入 60 01背包問題實例分析 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。 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)值。物品 i的 重量是 wi，其 價值為 vi，背包的容量為 C。 return k。 k = jk ? k+b[c[i]] : j+b[c[i]]。 in。 k = j+b[c[0]]。 else c[k ] = d[i].index。 in。 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。 d[i].index = i。 i++){ d[i].key = a[i]b[i]?b[i]:a[i]。 for(int i=0。 }。 int index。 1 2 3 4 5 6 A 2 5 7 10 5 2 B 3 8 4 11 3 4 55 int FlowShop(int n, int *a, int *b, int *c) { class Jobtype{ public: int operator= (Jobtype a) const //排序重載函數(shù) {return key=。 因此，在最壞情況下算法所需的計算時間為 O(nlogn)。 }。 流水作業(yè)調(diào)度問題的最優(yōu)值為 T(N,0)。 在一般情況下，機(jī)器 M1開始加工 S中作業(yè)時，機(jī)器 M2還在加工其它作業(yè)，要等時間 t后才可利用。 設(shè)全部作業(yè)的集合為 N={1， 2， … ， n}。 1 2 3 4 5 6 A 2 5 7 10 5 2 B 3 8 4 11 3 4 42 流水作業(yè)調(diào)度 直觀上，一個最優(yōu)調(diào)度應(yīng)使機(jī)器 M1沒有空閑時間，且機(jī)器 M2的空閑時間最少。 M1和 M2加工 作業(yè) i所需的時間分別為 ai和 bi。 1 2 3 4 5 6 a[i] 2 11 4 13 5 2 b(初值 =0) 2 11 7 20 15 13 sum 0 11 11 20 20 20 41 流水作業(yè)調(diào)度 n個作業(yè) {1， 2， … ， n}要在由 2臺機(jī)器 M1和 M2組成的流水線上完成加工。 } return sum。 else b=a[i]。i=n。 //sum是 bj(1≤j≤n)的最大值 int b=0。 則計算 bj的動態(tài)規(guī)劃遞歸式 bj=max{bj1+aj， aj}， 1≤j≤n。 } return sum。 if (sumleftsum) sum=leftsum。 if (rightsums2) s2=rightsum。i=right。rightsum=0。 if (leftsums1) s1=leftsum。i=left。leftsum=0。 int rightsum=MaxSubSum(a,center+1,right)。 else{int center=(left+right)/2。 1 n n/2 i j s1 s2 37 2. 分治方法求解 int MaxSubSum(int a[ ], int left, int right) { int sum=0。 } } } } 改進(jìn)后的算法復(fù)雜性為 O(n2) 。 besti=i。j++){ thissum+=a[j]。 for(j=i。i=n。bestj) { int sum=0。 由于有： 算法可作如下改進(jìn)： int MaxSum(int n, int *a, int amp。 } } return sum。 besti=i。k++) thissum+=a[k]。 for(k=i。j=n。i=n。bestj) { int sum=0。 35 1. 一個簡單算法 一個簡單算法： int MaxSum(int n, int *a, int amp。 } } return sum。 bes
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1