動態(tài)規(guī)劃ppt課件-閱讀頁
2024-11-18 18:12本頁面
【正文】 1。i++){ int thissum=0。j=n。 if(thissumsum){ sum=thissum。 bestj=j。 ?? ?????1jikkjjikk aaa36 ???????????????????inkkninnikknijikk asasnjnniaC121222211 m a xm a x12,21,.2. 分治方法求解 從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解： 如果將所給的序列 a[1:n]分為長度相等的兩段 a[1:n/1]和a[n/2+1:n]，分別求出這兩段的最大子段和，則 a[1:n]的最大子段和有三種情形： A. a[1:n]的最大子段和與 a[1:n/2]的最大子段和相同； B. a[1:n]的最大子段和與 a[n/2+1:n]的最大子段和相同； C. a[1:n]的最大子段和為下面的形式。 if (left==right)sum=a[left]0?a[left]:0。 int leftsum=MaxSubSum(a,left,center)。 int s1=0。 for (int i=center。i) { leftsum+=a[i]。 } int s2=0。 for (int i=center+1。i++) { rightsum+=a[i]。 } sum=s1+s2。 if (sumrightsum) sum=rightsum。 } 38 3. 動態(tài)規(guī)劃方法求解 在對上述分治算法的分析中我們注意到， bj是 1到 j位置的最大子段和 : 由 bj的定義易知，當 bj10時 bj=bj1+aj，否則 bj=aj。 jnjjikkjinjjkknjijikkjijbaanjab????????????????????????????111111m a xm a xm a xm a x1m a x 為，則所求的最大子段和，若記 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 39 3. 動態(tài)規(guī)劃方法求解 據(jù)此，可設(shè)計出求最大子段和的動態(tài)規(guī)劃算法如下： int MaxSum(int n, int a[]) { int sum=0。 for (int i=1。i++) { if (b0) b+=a[i]。 if (bsum) sum=b。 } 顯然該算法的計算時間為 O(n)。 每個作業(yè)加工的順序都是先在 M1上加工，然后在 M2上加工。 流水作業(yè)調(diào)度問題要求確定這 n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器 M1上開始加工，到最后一個作業(yè)在機器 M2上加工完成所需的 時間最少 。在一般情況下，機器M2上會有機器空閑和作業(yè)積壓 2種情況。 S N是N的 作業(yè)子集 。 將這種情況下完成 S中作業(yè)所需的最短時間記為 T(S,t)。 ?53 流水作業(yè)調(diào)度問題的 Johnson算法 (1) 令 (2) 將 N1中作業(yè)依 ai的非減序排序； 將 N2中作業(yè)依 bi的非增序排序； (3) N1中作業(yè)接 N2中作業(yè)構(gòu)成滿足 Johnson法則的最優(yōu)調(diào)度。|{},|{ 21 iiii baiNbaiN ????算法描述 N1中作業(yè)依 ai的非減序排序 N2中作業(yè)依 bi的非增序排序 1 2 3 4 5 6 A 2 5 7 10 5 2 B 3 8 4 11 3 4 54 算法描述 算法復(fù)雜度分析： 算法的主要計算時間花在對作業(yè)集的排序。 所需的空間為 O(n)。} int key。 bool job。 Jobtype *d=new Jobtype[n]。 in。 d[i].job = a[i]=b[i]。 } sort(d,n)。 for(int i=0。 i++){ if(d[i].job) c[j++] = d[i].index。 } j = a[c[0]]。 for(int i=1。 i++){ j += a[c[i]]。 } delete d。 //最優(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種物品和一背包。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的 總價值最大 ? 01背包問題是一個特殊的整數(shù)規(guī)劃問題。 ??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ì)，建立計算 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。 m[2][4]=max(m[3][4],m[3][1]+2)=5。 m[2][6]=max(m[3][6],m[3][3]+2)=5。 c n 61 由 01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，建立計算 m(i， j)的遞歸式如下 : 算法復(fù)雜度分析： 從 m(i， j)的遞歸式容易看出，算法需要 O(nc)計算時間。例如，當 c2n時，算法需要 Ω(n2 n)計算時間。 for( int j=0。 j++) m[n][j]=0。 j=c。 for( int i=n1。 i) { jMax=min(w[i]1,c)。 j=jMax。 for(int j=w[i]。 j++) m[i][j]=max(m[i+1][j], m[i+1][jw[i]]+v[i])。 if (c=w[1]) m[1][c]=max(m[1][c], m[2][cw[1]]+v[1])。 in。 else { x[i]=1。 } x[n]=(m[n][c]0)? 1:
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1