1、 1 最大子段和问题：给定整数序列 naaa , 21 ，求该序列形如 jik ka的子段和的最大值： jik knji a1m ax,0m ax1) 已知 一个简单算法如下： int Maxsum(int n,int a,int for(int i=1;i sum) sum = suma; besti = i; bestj = j; return sum; 试分析该算法的时间复杂性。 2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。 3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。 （提示：令1( ) m a x , 1
2、 , 2 , ,jki j n kib j a j n ） 解： 1） 分析按 照第一章，列出步数统计表，计算可得 )( 2nO 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的最大子段和为两部分的字段和组成，即jnjil nijaaaaa 122； intMaxSubSum ( int *a, int left , int right) int sum =0; if(
3、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; in
4、t right_sum =0; for ( int i = center +1; i s2) s2 = right_sum; sum = s1 + s2; if ( sum 0) b = b + a i; else b = a i; endif if( b sum) sum = b; j=i； endif return sum; 自行推导 ， 答案： 时间复杂度为 O（ n）。 2.动态规划算法的时间复杂度为 O（ n） （双机调度问题）用两台处理机 A和 B 处理 n 个作业。设第 i 个作业交给机器 A 处理时所需要的时间是 ia ，若由机器 B 来处理，则所需要的时间是 ib 。现在要求
5、每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这 n 个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法： )4,3,11,4,8,3(),(),2,5,10,7,5,2(),(,6 654321654321 bbbbbbaaaaaan 解： （思路一） 删除 （思路二）在 完成 前 k 个作业 时 ，设机器 A 工作 了 x 时间， 则 机器 B 最小的工作 时间是 x 的一个函 数 。 设 Fkx表示完成 前 k 个作业 时， 机器 B 最小的工作 时间 ， 则 )(1,)(1m in )(
6、kk axkFbxkFxkF 其中 kbxkF )(1 对应 第 k 个作业由机器 B 来处理（完成 k-1 个作业时机器 A工作 时间仍是 x，则 B 在 k-1 阶段用时为 )(1 xkF ） ；而 )(1 kaxkF 对应 第 k个作业由机器 A 处理（完成 k-1 个作业 ， 机器 A 工作 时间是 x-ak，而 B 完成 k阶段与完成 k-1 阶段用时相同为 )(1 kaxkF ）。 则完成前 k 个作业所需的时间为 )(,max xkFx 1）当处理第一个作业时， a1=2,b1=3; 机器 A 所花费时间的所有可能值范围： 0 x a0. x using namespace st
7、d; 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 = 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 j ? i : j; if(t
8、emp 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时间以内完
9、成 ,如果能 ,则把 pijk设为 true.经过了设置后 ,求对于 n个作业的所有可能的值为 pijn,对 min(max(i,j),结果为 15.即为所得到的结果 . 3考虑下面特殊的整数线性规划问题 nixbxaxciniiiniii1,2,1,0,m a x11 试设计一个解此问题 的动态规划算法，并分析算法的时间复杂度。 解 ： 方法 1. 设 ,21,1,0 niyi 令 niyyx niii 1, ，则上述规划问题转化为： niybyayc ini iini ii 21,1,0,m a x 2 12 1 ，其中 niaacc iniini 1, ， 把 ic 看作价值， ia 看
10、作重量， b 看作背包容量。 转化为 0/1 背包问题，所以可以 0/1 背包问题的 动态规划 算 法来求解。 由于 n 件物品的 0/1 背包的时间复杂性是 O（ 2n），则此时为 O（ 4n）。 方法 2. 可以看成是 另一种 背包问题。即 b 为背包容量， 2,1,0xi 为背包中可以装 0， 1，或者 2件物品， ix 对应的价值为 ic ，求在容量 b 一定的前提下，背包所容纳的物品的最大价值。也就是参数完全相同的两个 0-1 背包问题，它们同时制约于背包容量为 C 这个条件。 在设计算法时可以优先考虑 im ，也就是先判断背包剩下的容量能不能放进去 ic ，若可以再判断能否使 1ip ，若可以则就 再 放入一个 ic ，这样就间接满足了2 iii pmx 的条件。 0( 1 , ) ( , )xm k xm k x 递 推 式 ：0m a x ( 1 , ) , ( 1 , ) 2m a x ( 1 , ) , ( 1 , ) , ( 1 , 2 ) 2 2( 3 )kk k k kk k k k knxwm k x m k x w p w x wm k x m k x w p m k x w p x wO 时 间 复 杂 度 为（以上各题均来自同学们作业中的思想，仅供参考，自行整理答案。）
