动态规划算法习题答案——中国科学院

j

1．最大子段和问题：给定整数序列 a1,a2, ,an，求该序列形如 ak的子段和

k i

j

的最大值： max 0,max ak

1 i j nk i

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; } }

}

return sum;

}试分析该算法的时间复杂性。

2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。 3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。

j

（提示：令b(j) max

1 i j n

a

k i

k

,j 1,2, ,n

）

2

解：1）分析按照第一章，列出步数统计表，计算可得O(n)

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:n]的最大子段和相同； ③a[1:n]的最大子段和为两部分的字段和组成，即

j

a

l i

j

ai a n a n

2

1 2

aj；

动态规划算法习题答案——中国科学院

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) ; 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]; 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(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)

动态规划算法习题答案——中国科学院

j

j

1 i n1 j n

j

k

xa3）设b(j) m

1 i j

{ ak},则最大子段和为maxmax

k i

a

k i

maxmax

1 j n1 i j

a

k i

k

maxb(j).

1 j n

b(j) max{a1 aj 1 aj,a2 aj 1 aj, ,aj 1 aj,aj}

最大子段和实际就是max{b(1),b(2), ,b(n)}.

要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。

j

1 i j

j 1

1 i j 1

j 1

b(j) max{ ak} max{{ ak aj},aj} max{

k i

k i

1 i j 1

max{ ak} aj,aj} max{b(j 1) aj,aj}

k i

若b(j 1) 0, b(j) b(j 1) aj；

若b(j 1) 0，b(j) aj。

因此，计算b(j)的动态规划的公式为：b(j) max{b(j 1) aj,aj},1 j n.

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)

sum = b;

j=i； end{if}

}

return sum; }

自行推导，答案：时间复杂度为O（n）。

动态规划算法习题答案——中国科学院

2.动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是ai，若由机器B来处理，则所需要的时间是bi。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这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)

解：（思路一）在完成前k个作业时，设机器A工作了x时间，则机器B此时最小的工作时间是x的一个函数。

设F[k][x]表示完成前k个作业时，机器B最小的工作时间，则

F[k](x) min{F[k 1](x) bk,F[k 1](x ak)}

其中F[k 1](x) bk对应第k个作业由机器B来处理（完成k-1个作业时机器A工作时间仍是x，则B在k-1阶段用时为F[k 1](x)）；而F[k 1](x ak)对应第k个作业由机器A处理（完成k-1个作业，机器A工作时间是x-a[k]，而B完成k阶段与完成k-1阶段用时相同为F[k 1](x ak)）。

则完成前k个作业所需的时间为max{x,F[k](x)} 1）当处理第一个作业时，a[1]=2,b[1]=3;

机器A所花费时间的所有可能值范围：0 x a[0]. x<0时，设F[0][x]= ∞，则max(x, ∞)= ∞； 0 x<2时，F[1][x]=3，则Max(0,3)=3， x 2时， F[1][x]= 0，则Max(2,0)=2；

2）处理第二个作业时：x的取值范围是：0 <= x <= (a[0] + a[1])， 当x<0时，记F[2][x] = ∞；以此类推下去

（思路二）假定n个作业的集合为Sn 1,2, ,n 。

设J为Sn的子集，若安排J中的作业在机器A上处理，其余作业在机器B上处

a,理，此时所用时间为T(J) max

j

j J

b， j j S\J

动态规划算法习题答案——中国科学院

则双机处理作业问题相当于确定Sn的子集J，使得安排是最省时的。即转化为求J使得 …… 此处隐藏：4567字，全部文档内容请下载后查看。喜欢就下载吧 ……