5-动态规划算法习题答案.docVIP

PAGE

1．最大子段和问题：给定整数序列，求该序列形如的子段和的最大值：

已知一个简单算法如下：

intMaxsum(intn,inta,intbesti,intbestj){

intsum=0;

for(inti=1;i=n;i++){

intsuma=0;

for(intj=i;j=n;j++){

suma+=a[j];

if(sumasum){

sum=suma;

besti=i;

bestj=j;

}

}

}

returnsum;

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

试用分治算法解最大子段和问题，并分析算法的时间复杂性。

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

（提示：令）

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

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]的最大子段和为两部分的字段和组成，即；

intMaxSubSum(int*a,intleft,intright){

intsum=0;

if(left==right)

sum=a[left]0?a[left]:0;

else

{intcenter=(left+right)/2;

intleftsum=MaxSubSum(a,left,center);

intrightsum=MaxSubSum(a,center+1,right);

ints_1=0;

intleft_sum=0;

for(inti=center;i=left;i--){

left_sum+=a[i];

if(left_sums1)

s1=left_sum;

}

ints2=0;

intright_sum=0;

for(inti=center+1;i=right;i++){

right_sum+=a[i];

if(right_sums2)

s2=right_sum;

}

sum=s1+s2;

if(sumleftsum)

sum=leftsum;

if(sumrightsum)

sum=rightsum;

}

returnsum;

}

intMaxSum2(intn){

inta；

returnMaxSubSum(a,1,n);

}该算法所需的计算时间T(n)满足典型的分治算法递归分式

T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)

3）设,则最大子段和为

最大子段和实际就是.

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

若,；

若，。

因此，计算的动态规划的公式为：

intMaxSum(int*a，intn)

{

intsum=0,b=0，j=0;

for(inti=1;i=n;i++)

{if(b0)

b=b+a[i];

else

b=a[i];

end{if}

if(bsum)

sum=b;

j=i；

end{if}

}

returnsum;

}

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

动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：

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