5 动态规划算法

1最大子段和问题：给定整数序列 ，求该序列形如的子段和的最大值： 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 sum) sum = suma; besti = i; bestj = j; return sum;试分析该算法的时间复杂性。2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。（提示：令）解：1）分析按照第一章，列出步数统计表，计算可得 2）分治算法：将所给的序列a1:n分为两段a 1:n/2、an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有三种可能：a1:n的最大子段和与a1:n/2的最大子段和相同；a1:n的最大子段和与an/2+1:n的最大子段和相同；a1:n的最大子段和为两部分的字段和组成，即；intMaxSubSum ( int *a, int left , int right)int sum =0;if( left=right) sum = aleft 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 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)3）设,则最大子段和为最大子段和实际就是.要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。 若, ；若，。因此，计算的动态规划的公式为：intMaxSum (int* a，int n )int sum = 0, b = 0，j=0;for( int i=1;i0)b = b + a i;elseb = a i; endifif( b sum)sum = b; j=i； endifreturn sum;自行推导，答案：时间复杂度为O（n）。2. 动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：解：（思路一）设为完成前i个作业，系统所需的最短处理时间，表示在完成前i个作业所需时间最少的策略下，分配到A机器上处理的作业的时间，表示在完成前i个作业所需时间最少的策略下，分配到B机器上处理的作业的时间得到的递推公式，其中。直接的关系式即是，其中为了方便，得到算法如下：int minTime(int *a, int *b, int n)/a,b为A,B机器上处理作业所用时间数组 int sa=0;/sa表示分配到A机器上处理的作业的最短总时间 int sb=0;/sb表示分配到B机器上处理的作业的最短总时间 int T=0; /T为最短总的处理时间 for(int i;in;i+) if(sa+aiT) /式(1)中的情况3 sa+=ai; T=sa; else if(sb+biT) /式(1)中的情况2 sb+=bi; T=sb; Else /式(1)中的情况1 if(sa+aisb+bi)&(sa+aiT) sa+=ai; else(sb+bi sa+ai)&(sb+biT) sb+=bi; return T; 算法中只存在有一个for循环，for循环里面的语句最多执行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, 满足式中(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个作业时，设机器A工作了x时间，则机器B最小的工作时间是x的一个函数。设Fkx表示完成前k个作业时，机器B最小的工作时间，则其中对应第k个作业由机器B来处理（完成k-1个作业时机器A工作时间仍是x，则B在k-1阶段用时为）；而对应第k个作业由机器A处理（完成k-1个作业，机器A工作时间是x-ak，而B完成k阶段与完成k-1阶段用时相同为）。则完成前k个作业所需的时间为1）当处理第一个作业时，a1=2,b1=3;机器A所花费时间的所有可能值范围：0 x a0.x0时，设F0x= ，则max(x, )= ；0x2时，F1x=3，则Max(0,3)=3，x2时， F1x= 0，则Max(2,0)=2；2）处理第二个作业时：x的取值范围是：0 = x = (a0 + a1)，当x0时，记F2x = ；以此类推下去（思路三）假定个作业的集合为。设为的子集，若安排中的作业在机器A上处理，其余作业在机器B上处理，此时所用时间为，则双机处理作业问题相当于确定的子集，使得安排是最省时的。即转化为求使得。若记，则有如下递推关系：（思路四）此问题等价于求（x1,xn），使得它是下面的问题最优解。min maxx1a1+xnan，(1-x1)b1+(1-xn)bn xi=0或1，i=1n基于动态规划算法的思想，对每个任务i，依次计算集合S(i)。其中每个集合中元素都是一个3元组（F1,F2,x）。这个3元组的每个分量定义为F1:处理机A的完成时间F2：处理机B的完成时间x：任务分配变量。当xi=1时表示将任务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=max2+5+10+2,7+5=19。然后，依次考虑任务i，i=1n。在分配任务i时，只有2种情形，xi=1或xi=0。此时，令S(i)=S(i-1)+(ai,0,2i)US(i-1)+(0,bi,0)在做上述集合并集的计算时，遵循下面的原则：当（a,b,c）,(d,e,f)S(i)且a=d,b=e时，仅保留（a,b,c）；仅当maxa,b=F时，(a,b,c)S(i)最后在S(n)中找出使maxF1,F2达到最小的元素，相应的x即为所求的最优解，其最优值为maxF1,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,1,0,1）因此，F=max2+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), (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)所以，完成所有作业最短时间是15，安排有三种：（1,1,0,0,1,1），（1,0,0,1,0,1）,(0,1,0,1,0,0)（思路五）C+ 源代码如下:#include using namespace std;const int MAXS = 70;const int MAXN = 10;bool pMAXSMAXSMAXS;int aMAXS,bMAXS;int schduleDyn(int * a,int * b,int n,int mn)int i,j,k;/=数组初始化=for(i = 0; i = mn; i+)for(j = 0; j = mn; j+)pij0 = true;for(k = 1 ; k = n; k+)pijk = false;/=动态递归=for(k = 1; k = n; k +)for(i = 0; i = mn; i+)for(j = 0; j = 0) pijk = pi - ak-1jk-1;if( (j - bk-1) = 0)pijk = (pijk | pij-bk-1k-1);/=求结果=int rs = mn;int temp = 0;for(i = 0; i = mn; i+)for(j = 0; j j ? i : j;if(temp n;for(i = 0; i ai;if(ai m)m = ai;for(i = 0; i bi;if(bi m)m = bi;mn = m * n;/=动态规划求解=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);由于求解过程比较繁锁,这里只说个大概算法执行过程,首先,用pijk,记录下对于第k个作业,能否在对于a机器是i时间以内,对于b机器是j时间以内完成,如果能,则把pijk设为true.经过了设置后,求对于n个作业的所有可能的值为pijn,对min(max(i,j),结果为15.即为所得到的结果.3考虑下面特殊的整数线性规划问题试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。解：方法1.设令，则上述规划问题转化为：，其中，把看作价值，看作重量，看作背包容量。转化为0/1背包问题，所以可以0/1背包问题的动态规划算法来求解。由于n件物品的0/1背包的时间复杂性是O（2n），则此时为O（4n）。方法2. 可以看成是另一种背包问题。即b为背包容量，为背包中可以装0，1，或者2件物品，对应的价值为，求在容量b 一定的前提下，背包所容纳的物品的最大价值。也就是参数完全相同的两个0-1背包问题，它们同时制约于背包容量为C这个条件。在设计算法时可以优先考虑，也就是先判断背包剩下的容量能不能放进去，若可以再判断能否使，若可以则就再放入一个，这样就间接满足了的条件。（以上各题均来自同学们作业中的思想，仅供参考，自行整理答案。）