《5 動態(tài)規(guī)劃算法》由會員分享，可在線閱讀，更多相關《5 動態(tài)規(guī)劃算法（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 1．最大子段和問題：給定整數(shù)序列 ，求該序列形如的子段和的最大值： 1) 已知一個簡單算法如下： int Maxsum(int n,int a,int& best i,int& bestj){ int sum = 0; for(int i=1;i<=n;i++){ int suma = 0; for(int j=i;j<=n;j++){ suma + = a[j]; if(suma > sum){ sum = suma; besti = i; bestj = j; } }

2、 } return sum; }試分析該算法的時間復雜性。 2) 試用分治算法解最大子段和問題，并分析算法的時間復雜性。 3) 試說明最大子段和問題具有最優(yōu)子結構性質，并設計一個動態(tài)規(guī)劃算法解最大子段和問題。分析算法的時間復雜度。 （提示：令） 解：1）分析按照第一章，列出步數(shù)統(tǒng)計表，計算可得 2）分治算法：將所給的序列a[1:n]分為兩段a [1:n/2]、a[n/2+1:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有三種可能： ①a[1:n]的最大子段和與a[1:n/2]的最大子段和相同； ②a[1:n]的最大子段和與a[n/2+1

3、:n]的最大子段和相同； ③a[1:n]的最大子段和為兩部分的字段和組成，即； intMaxSubSum ( int *a, int left , int right){ 　int sum =0; 　if( left==right) 　　 sum = a[left] > 0? a[ left]:0 ; else 　 {int center = ( left + right) /2; int leftsum =MaxSubSum ( a, left , center) ; 　　 int rightsum =MaxSubSum ( a, center +1, right)

4、; 　　 int s_1 =0; 　　 int left_sum =0; 　　 for ( int i = center ; i >= left; i--){ 　　　 left_sum + = a [ i ]; 　　　 if( left_sum > s1) 　　　　 s1 = left_sum; 　　 } 　　 int s2 =0; 　　 int right_sum =0; 　　 for ( int i = center +1; i <= right ; i++){ 　　 　right_sum + = a[ i]; 　　　

5、 if( right_sum > s2) 　　　　 s2 = right_sum; 　　 } 　　 sum = s1 + s2; 　　 if ( sum < leftsum) 　　　 sum = leftsum; 　　 if ( sum < rightsum) 　　　 sum = rightsum; } 　 return sum; } int MaxSum2 (int n){ int a； 　 returnMaxSubSum ( a, 1, n) ; } 該算法所需的計算時間T(n)滿足典型的分治算法遞歸分式 T(n)=2T

6、(n/2)+O(n)，分治算法的時間復雜度為O(nlogn) 3）設,則最大子段和為 最大子段和實際就是. 要說明最大子段和具有最優(yōu)子結構性質，只要找到其前后步驟的迭代關系即可。 若, ； 若，。 因此，計算的動態(tài)規(guī)劃的公式為： intMaxSum (int* a，int n ) { int sum = 0, b = 0，j=0; for( int i=1;i<=n;i++) { if( b >0) 　　 b = b + a [i]; 　 else 　　 b = a [i]; end{if} 　 if( b > sum) 　

7、　 sum = b; j=i； end{if} } return sum; } 自行推導，答案：時間復雜度為O（n）。 2. 動態(tài)規(guī)劃算法的時間復雜度為O（n）（雙機調度問題）用兩臺處理機A和B處理個作業(yè)。設第個作業(yè)交給機器A處理時所需要的時間是，若由機器B來處理，則所需要的時間是?，F(xiàn)在要求每個作業(yè)只能由一臺機器處理，每臺機器都不能同時處理兩個作業(yè)。設計一個動態(tài)規(guī)劃算法，使得這兩臺機器處理完這個作業(yè)的時間最短（從任何一臺機器開工到最后一臺機器停工的總的時間）。以下面的例子說明你的算法： 解：（思路一） 設為完成前i個作業(yè)，系統(tǒng)所需的最

8、短處理時間， 表示在完成前i個作業(yè)所需時間最少的策略下，分配到A機器上處理的作業(yè)的時間， 表示在完成前i個作業(yè)所需時間最少的策略下，分配到B機器上處理的作業(yè)的時間 得到的遞推公式， 其中。 直接的關系式即是， 　　　　　　， 其中為了方便，， 得到算法如下： 　　　int minTime(int *a, int *b, int n)　　//a,b為A,B機器上處理作業(yè)所用時間數(shù)組 { int sa=0;　　　　　　　　　//sa表示分配到A機器上處理的作業(yè)的最短總時間 int sb=0;　　　　　　　　　//sb表

9、示分配到B機器上處理的作業(yè)的最短總時間 int T=0; //T為最短總的處理時間 for(int i;iT)) //式(1)中的情況3 { sa+=a[i]; T=sa; } else if((sb+b[i]T)) //式(1)中的情況2 { sb+=b[i];

10、T=sb; } Else //式(1)中的情況1 { if((sa+a[i]

11、 } 算法中只存在有一個for循環(huán)，for循環(huán)里面的語句最多執(zhí)行2*n次，從而得到算法的時間復雜度為O(n)。 用題中的實例分析算法n=6,(a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4) i=1, 滿足式中(1)中的第三條，得：sa=2,sb=0,T=2; i=2, 滿足式中(1)中的第三條，得：sa=7,sb=0,T=7; i=3, 滿足式中(2)中的第三條，得：sa=7,sb=4,T=7; i=4, 滿足式中(

12、2)中的第三條，得：sa=7,sb=15,T=15; i=5, 滿足式中(1)中的第三條，得：sa=12,sb=15,T=15; i=6, 滿足式中(1)中的第三條，得：sa=14,sb=15,T=15; 得到最短的T為15。 （思路二）在完成前k個作業(yè)時，設機器A工作了x時間，則機器B最小的工作時間是x的一個函數(shù)。 設F[k][x]表示完成前k個作業(yè)時，機器B最小的工作時間，則 其中對應第k個作業(yè)由機器B來處理（完成k-1個作業(yè)時機器A工作時間仍是x，則B在k-1階段用時為）；而對應第k個作業(yè)由機器A處理（完成k-1個作業(yè)，機器A工作時間是

13、x-a[k]，而B完成k階段與完成k-1階段用時相同為）。 則完成前k個作業(yè)所需的時間為 1）當處理第一個作業(yè)時，a[1]=2,b[1]=3; 機器A所花費時間的所有可能值范圍：0 ￡x ￡a[0]. x<0時，設F[0][x]= ∞，則max(x, ∞)= ∞； 0￡x<2時，F(xiàn)[1][x]=3，則Max(0,3)=3， x32時， F[1][x]= 0，則Max(2,0)=2； 2）處理第二個作業(yè)時：x的取值范圍是：0 <= x <= (a[0] + a[1])， 當x<0時，記F[2][x] = ∞；以此類推下去 （思路三）假定個作業(yè)的集合為。 設為的子集，若安

14、排中的作業(yè)在機器A上處理，其余作業(yè)在機器B上處理，此時所用時間為， 則雙機處理作業(yè)問題相當于確定的子集，使得安排是最省時的。即轉化為求使得。若記，則有如下遞推關系： （思路四） 此問題等價于求（x1,……xn），使得它是下面的問題最優(yōu)解。 min max{x1a1+……xnan，(1-x1)b1+……+(1-xn)bn} xi=0或1，i=1~n 基于動態(tài)規(guī)劃算法的思想，對每個任務i，依次計算集合S(i)。其中每個集合中元素都是一個3元組（F1,F2,x）。這個3元組的每個分量定義為 F1:處理機A的完成時間 F2：處理機B的完成時間 x：任務分配變量。當xi=1時表示將任

15、務i分配給處理機A，當xi=0時表示分配給處理機B。 初始時，S(0)={(0,0,0)} 令F=按處理時間少的原則來分配任務的方案所需的完成時間。 例如，當（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)時，按處理時間少的原則分配任務的方案為（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1） 因此，F(xiàn)=max{2+5+10+2,7+5}=19。 然后，依次考慮任務i，i=1~n。在分配任務i時，只有2種情形，xi=1或xi=0。此時，令S(i)={S(i-1)+(ai,0,2

16、i)}U{S(i-1)+(0,bi,0)}在做上述集合并集的計算時，遵循下面的原則： ①當（a,b,c）,(d,e,f)?S(i)且a=d,b<=e時，僅保留（a,b,c）； ②僅當max{a,b}<=F時，(a,b,c)?S(i) 最后在S(n)中找出使max{F1,F2}達到最小的元素，相應的x即為所求的最優(yōu)解，其最優(yōu)值為max{F1,F2}。 當（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)時, 按處理時間少的原則分配任務的方案為（x1,x2,x3,x4,x5,x6）=（1,1,0,

17、1,0,1） 因此，F(xiàn)=max{2+5+10+2,7+5}=19。 S(0)={(0,0,0)}; S(1)={(2,0,2),(0,3,0)} S(2)={(7,0,6),(5,3,4),(2,8,2),(0,11,0)} S(3)={(14,0,14),(12,3,12),(9,8,10), (7,4,6), (5,7,4),(2,12,2),(0,15,0)} S(4)={(19,8,26), (17,4,22),(15,7,20),(12,12,18),(14,11,14),(9,19,10),(7,15,6),(5,18,4)} S(5)={ (19,11,46),

18、(12,15,38), (19,11,26), (17,7,22), (15,10,20),(12,15,18),(14,14,14),(7,18,6)} S(6)={ (14,15,102),(19,7,86),(17,10,84),(14,15,82), (9,18,70),(12,19,38), (15,14,20),(12,19,18)} max(F1,F2)最小的元組為(14,15,102), (14,15,82), (15,14,20) 所以，完成所有作業(yè)最短時間是15，安排有三種： （1,1,0,0,1,1），（1,0,0,1,0,1）,(0,1,0,1,0,0) （

19、思路五）C++ 源代碼如下: #include using namespace std; const int MAXS = 70; const int MAXN = 10; bool p[MAXS][MAXS][MAXS]; int a[MAXS],b[MAXS]; int schduleDyn(int * a,int * b,int n,int mn) { int i,j,k; //===========數(shù)組初始化=================== for(i = 0; i <= mn; i++) for(j = 0; j <= mn;

20、 j++) { p[i][j][0] = true; for(k = 1 ; k <= n; k++) p[i][j][k] = false; } //===========動態(tài)遞歸============= for(k = 1; k <= n; k ++) for(i = 0; i <= mn; i++) for(j = 0; j <= mn; j++) { if( (i - a[k-1]) >= 0) p[i][j][k] = p[i - a[k-1]][j][k-1]; if( (j - b[k-1])

21、>= 0) p[i][j][k] = (p[i][j][k] | p[i][j-b[k-1]][k-1]); } //================求結果===================== int rs = mn; int temp = 0; for(i = 0; i <= mn; i++) for(j = 0; j <= mn ; j++) {if(p[i][j][n]) { temp = i > j ? i : j; if(temp < rs) rs = temp; } } retu

22、rn rs; } void main() { int i,n,m = 0,mn = 0; //=============初始化======================== cin >> n; for(i = 0; i < n; i++) { cin >> a[i]; if(a[i] > m) m = a[i]; } for(i = 0; i < n; i++) { cin >> b[i]; if(b[i] > m) m = b[i]; } mn = m * n; //=========動態(tài)規(guī)劃求解=====

23、============ cout << schduleDyn(a,b,n,mn) << endl; system("pause"); } 對于例子: n = 6 ;(a1,….,a6) = (2 5 7 10 5 2),(b,1…,b6) = (3 8 4 11 3 4); 由于求解過程比較繁鎖,這里只說個大概算法執(zhí)行過程,首先,用p[i][j][k],記錄下對于第k個作業(yè),能否在對于a機器是i時間以內,對于b機器是j時間以內完成,如果能,則把p[i][j][k]設為true.經(jīng)過了設置后,求對于n個作業(yè)的所有可能的值為p[i][j][n],對min(max(i,j)),結果

24、為15.即為所得到的結果. 3．考慮下面特殊的整數(shù)線性規(guī)劃問題 試設計一個解此問題的動態(tài)規(guī)劃算法，并分析算法的時間復雜度。 解：方法1. 設令，則上述規(guī)劃問題轉化為： ，其中， 把看作價值，看作重量，看作背包容量。 轉化為0/1背包問題，所以可以0/1背包問題的動態(tài)規(guī)劃算法來求解。由于n件物品的0/1背包的時間復雜性是O（2n），則此時為O（4n）。 方法2. 可以看成是另一種背包問題。即b為背包容量，為背包中可以裝0，1，或者2件物品，對應的價值為，求在容量b 一定的前提下，背包所容納的物品的最大價值。也就是參數(shù)完全相同的兩個0-1背包問題，它們同時制約于背包容量為C這個條件。 在設計算法時可以優(yōu)先考慮，也就是先判斷背包剩下的容量能不能放進去，若可以再判斷能否使，若可以則就再放入一個，這樣就間接滿足了的條件。 （以上各題均來自同學們作業(yè)中的思想，僅供參考，自行整理答案。）