下载文档原格式
算法设计技巧与分析习题答案【篇一：算法设计与分析考试题及答案】一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列x={b,c,a,d,b,c,d}，y={a,c,b,a,b,d,c,d}，请给出序列x和y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
二、综合题（50分）1.写出设计动态规划算法的主要步骤。
2.流水作业调度问题的johnson算法的思想。
3.若n=4，在机器m1和m2上加工作业i所需的时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，c=9，v={6,10,3}，w={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
Program算法设计与分析基础中文版答案习题5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次..对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.(农夫过河)P—农夫 W—狼 G—山羊 C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBin(n).n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 MinDistance(A[0..n-1])n-1]a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element., 0 for an array of positive numbers ) to mark the i th position is empty. (“lazy deletion”)第2章习题7.对下列断言进行证明:(如果是错误的,请举例)a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n))b.α>0时,Θ(αg(n))= Θ(g(n))解:a. 这个断言是正确的。
2-34、Gray码是一个长度为2n的序列。
序列中无相同元素。
每个元素都是长度为n位的串。
相邻元素恰好只有一位不同。
用分治策略设计一个算法对任意的n构造相应的Gray码。
答：设序列中元素由0、1组成。
当 n=1 时 Gray码的序列有2个元素（21=2），分别为：0，| 1当 n=2 时 Gray码的序列有4个元素（22=4），分别为：00，10，| 11，01当 n=3 时 Gray码的序列有8个元素（23=8），分别为：000，100，110，010，| 011，111，101，001当 n=4 时 Gray码的序列有16个元素（24=16），分别为：0000，1000、1100、0100，0110，1110，1010，0010，| 0011，1011，1111，0111，0101，1101，1001，0001从上面的列举可得如下规律：n=k时，Gray码的序列有2k个元素，分别为：n=k-1时的Gray码元素正向后加0，得前2k-1个元素，反向后加1的后2k-1个元素。
如 n=2时 Gray码序列的4个元素分别为：00，10， 11，01当 n=3 时 Gray码序列的前4个元素（23=8），分别为：000，100，110，010是n=2时Gray码四个元素正向后加0，即：000，100， 110，010Gray码序列的后4个元素（23=8），分别为：011，111，101，001 是n=2时Gray码四个元素反向后加1，n=2时Gray码四个元素：00，10， 11，01即：011，111，101，001可以看出，Gray码可以用分治策略，递归实现，2n的Gray码可以用2n-1的Gray码构成。
算法描述：void Gray( type a[],int n){ char a[];if (n==1) { a[0]=’0’;a[1]=’1’;}if (n>1){ Gray(a[],n-1);int k=2n-1-1; //Gray码的个数，因为数组下标从0开始int i=k;for (int x=k;x>=0;x--){char y=a[x];a[x]=y+’0’;a[i+1]=y+’1’; i++;}}}3-7 给定由n个英文单词组成的一段文章，……答：设由n 个单词组成的一段文章可以表示为 A[1:n]，它的“漂亮打印”方案记为B[1:n]，构成该最优解的最小空格数（最优值）记为m[1][n]（1）分析最优解的结构：A[1:n]的最优解B[1:n]，必然在第k个单词处断开，那么A[1:k]是“漂亮打印”，并且A[k+1:n]也是“漂亮打印”。
习题11. 图论诞生于七桥问题。
出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。
七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。
请将该问题的数据模型抽象出来，并判断此问题是否有解。
七桥问题属于一笔画问题。
输入：一个起点输出：相同的点1， 一次步行2， 经过七座桥，且每次只经历过一次3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。
另一类是只有二个奇点的图形。
2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。
请用伪代码描述这个版本的欧几里德算法=m-n2.循环直到r=0m=nn=rr=m-n3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求分别给出伪代码和C++描述。
编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。
#include<iostream>using namespace std;int main(){double value=0;图 七桥问题for(int n=1;n<=10000 ;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<<n<<endl;break;}}计算π值的问题能精确求解吗编写程序，求解满足给定精度要求的π值#include <iostream>using namespace std;int main (){double a,b;double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。
为什么是6天呢任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。
算法设计与分析常见习题及详解⽆论在以后找⼯作还是⾯试中，都离不开算法设计与分析。
本博⽂总结了相关算法设计的题⽬，旨在帮助加深对贪⼼算法、动态规划、回溯等算法的理解。
1、计算下述算法执⾏的加法次数：输⼊：n =2^t //t 为整数输出：加法次数 k K =0while n >=1 do for j =1 to n do k := k +1 n = n /2return k解析：第⼀次循环执⾏n次加法，第⼆次循环执⾏1/2次加法，第三次循环执⾏1/次加法…因此，上述算法执⾏加法的次数为==2n-12、考虑下⾯每对函数 f(n) 和 g(n) ，如果它们的阶相等则使⽤Θ记号，否则使⽤ O 记号表⽰它们的关系解析：前导知识：，因为解析：，因为解析:，因为解析：解析:3、在表1.1中填⼊ true 或 false解析：利⽤上题的前导知识就可以得出。
2=21/4n +n +21n +41...+1n +n −n +21n −21n +41....−1f (n )=(n −2n )/2，g (n )=6n1<logn <n <nlogn <n <2n <32<n n !<n ng (n )=O (f (n ))f (n )=Θ(n ),g (n )=2Θ(n )f (n )=n +2,g (n )=n n 2f (n )=O (g (n ))f (n )=Θ(n ),g (n )=Θ(n )2f (n )=n +nlogn ,g (n )=n nf (n )=O (g (n ))f (n )=Θ(nlogn ),g (n )=Θ(n )23f (n )=2(log ),g (n )=n 2logn +1g (n )=O (f (n ))f (n )=log (n !),g (n )=n 1.05f (n )=O (g (n ))4、对于下⾯每个函数 f(n),⽤f(n) =Θ(g(n))的形式，其中g(n)要尽可能简洁，然后按阶递增序排列它们（最后⼀列）解析：最后⼀个⽤到了调和公式：按阶递增的顺序排列：、、、、、、、、、(n −2)!=Θ((n −2)!)5log (n +100)=10Θ(logn )2=2n Θ(4)n 0.001n +43n +31=Θ(n )4(lnn )=2Θ(ln n )2+3n logn =Θ()3n 3=n Θ(3)n log (n !)=Θ(nlogn )log (n )=n +1Θ(nlogn )1++21....+=n1Θ(logn )=∑k =1nk 1logn +O (1)1++21....+n 15log (n +100)10(lnn )2+3n logn log (n !)log (n )n +10.001n +43n +313n 22n (n −2)!5、求解递推⽅程前导知识：主定理前导知识：递归树：例⼦：递归树是⼀棵节点带权的⼆叉树，初始递归树只有⼀个结点，标记为权重W(n)，然后不断进⾏迭代，最后直到树种不再含有权为函数的结点为⽌，然后将树根结点到树叶节点的全部权值加起来，即为算法的复杂度。
算法实现题3-7 数字三角形问题问题描述：给定一个由n行数字组成的数字三角形，如图所示。
试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。
数据输入：有文件input.txt提供输入数据。
文件的第1行是数字三角形的行数n，1<=n<=100。
接下来的n行是数字三角形各行的数字。
所有数字在0-99之间。
结果输出：程序运行结束时，将计算结果输出到文件output.txt中。
文件第1行中的数是计算出的最大值。
输入文件示例输出文件示例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5源程序：#include "stdio.h" voidmain(){ intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量in=fopen("input.txt","r");fscanf(in,"%d",&n);//将行数n读入到变量n中for(i=0;i<n;i++)//将各行数值读入到数组triangle中for(j=0;j<=i;j++)fscanf(in,"%d",&triangle[i][j]);for(int row=n-2;row>=0;row--)//从上往下递归计算for(int col=0;col<=row;col++)if(triangle[row+1][col]>triangle[row+1][col+1])triangle[row][col]+=triangle[row+1][col];elsetriangle[row][col]+=triangle[row+1][col+1];out=fopen("output.txt","w");fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 }算法实现题4-9 汽车加油问题问题描述：一辆汽车加满油后可行驶nkm。
习题5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d 能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次..对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.(农夫过河)P—农夫 W—狼 G—山羊 C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBin(n).n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 MinDistance(A[0..n-1])n-1]a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the ith element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element., 0 for an array of positive numbers ) to mark the ith position is empty. (“lazy deletion”)习题1欧几里得算法的时间复杂度欧几里得算法, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式gcd(a, b) = gcd(b, a mod b)其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b的余数. 算法如下:输入: 两个整数a, b输出: a和b的最大公约数function gcd(a, b:integer):integer;if b=0 return a;else return gcd(b, a mod b);end function欧几里得算法是最古老而经典的算法, 理解和掌握这一算法并不难, 但要分析它的时间复杂度却并不容易. 我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论), 我们只考虑这样的问题: 欧几里得算法在最坏情况下所需的模运算次数和输入的a和b的大小有怎样的关系?我们不妨设a>b>=1(若a<b我们只需多做一次模运算, 若b=0或a=b模运算的次数分别为0和1), 构造数列{un}: u0=a, u1=b, uk=uk-2 mod uk-1(k>=2), 显然, 若算法需要n次模运算, 则有un=gcd(a, b), un+1=0. 我们比较数列{un}和菲波那契数列{Fn}, F0=1<=un, F1=1<=un-1, 又因为由uk mod uk+1=uk+2, 可得uk>=uk+1+uk+2, 由数学归纳法容易得到uk>=Fn-k, 于是得到a=u0>=Fn, b=u0>=Fn-1. 也就是说如果欧几里得算法需要做n次模运算, 则b必定不小于Fn-1. 换句话说, 若 b<Fn-1, 则算法所需模运算的次数必定小于n. 根据菲波那契数列的性质, 有Fn-1>n/sqrt(5), 即b>n/sqrt(5), 所以模运算的次数为O(lgb)---以b为底数 = O(lg(2)b)---以2为底数，输入规模也可以看作是b的bit位数。
1．最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如 jik k a 的子段和的最大值：ji k k n j i a 1max ,0max1) 已知一个简单算法如下：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) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。
分析算法的时间复杂度。
（提示：令1()max,1,2,,jki j nk ib j a j n L ）解：1）分析按照第一章，列出步数统计表，计算可得)(2n O2）分治算法：将所给的序列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 n jil n i ja a a a a122；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)3）设}{max )(1 j ik k ji a j b ,则最大子段和为).(max max max max max 11111j b a a nj jik k ji n j j ik k nj n i},,,,max {)(11211j j j j j j j a a a a a a a a a j b最大子段和实际就是)}(,),2(),1(max{n b b b .要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。
},)1(max {},}{max max {},}{max {}{max )(1111111j j j j j ik k j i j j i j j i k k ji k k j i a a j b a a a a a a a j b若0)1( j b , j a j b j b )1()(；若0)1( j b ，j a j b )(。
因此，计算)(j b 的动态规划的公式为：.1},,)1(max {)(n j a a j b j b j jintMaxSum (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];elseb = 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 处理时所需要的时间是i a ，若由机器B 来处理，则所需要的时间是i b 。
现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。
设计一个动态规划算法，使得这两台机器处理完这n 个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。
以下面的例子说明你的算法：)4,3,11,4,8,3(),,,,,(),2,5,10,7,5,2(),,,,,(,6654321654321 b b b b b b a a a a a a n解：（思路一）删除（思路二）在完成前k 个作业时，设机器A 工作了x 时间，则机器B 最小的工作时间是x 的一个函数。
设F[k][x]表示完成前k 个作业时，机器B 最小的工作时间，则)}](1[,)](1[m in{)]([k k a x k F b x k F x k F其中k b x k F )](1[对应第k 个作业由机器B 来处理（完成k-1个作业时机器A 工作时间仍是x ，则B 在k-1阶段用时为)](1[x k F ）；而)](1[k a x k F 对应第k 个作业由机器A 处理（完成k-1个作业，机器A 工作时间是x-a[k]，而B 完成k 阶段与完成k-1阶段用时相同为)](1[k a x k F ）。
则完成前k 个作业所需的时间为)}]([,max{x k F 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 个作业的集合为 n S n ,,2,1 。
设J 为n S 的子集，若安排J 中的作业在机器A 上处理，其余作业在机器B 上处理，此时所用时间为J S j j Jj j b a J T \,max )(， 则双机处理作业问题相当于确定n S 的子集J ，使得安排是最省时的。
即转化为求J 使得)}({min J T nS J 。
若记 1,,2,11 n S n ，则有如下递推关系：J S j j n J j j S J J S j j J j j n S J I S j j I j j S I b b a b a a b a n n n \\\,max min ,,max min min ,max min 11－－（思路四）此问题等价于求（x 1,……x n ），使得它是下面的问题最优解。
min max{x 1a 1+……x n a n ，(1-x 1)b 1+……+(1-x n )b n } x i =0或1，i=1~n基于动态规划算法的思想，对每个任务i ，依次计算集合S (i)。
其中每个集合中元素都是一个3元组（F 1,F 2,x ）。
这个3元组的每个分量定义为 F 1:处理机A 的完成时间 F 2：处理机B 的完成时间 x ：任务分配变量。
当x i =1时表示将任务i 分配给处理机A ，当x i =0时表示分配给处理机B 。
初始时，S (0)={(0,0,0)}令F=按处理时间少的原则来分配任务的方案所需的完成时间。
例如，当（a 1，a 2,a 3,a 4,a 5,a 6）=(2,5,7,10,5,2),(b 1,b 2,b 3,b 4,b 5,b 6)=(3,8,4,11,3,4)时，按处理时间少的原则分配任务的方案为（x 1,x 2,x 3,x 4,x 5,x 6）=（1,1,0,1,0,1） 因此，F=max{2+5+10+2,7+5}=19。
然后，依次考虑任务i ，i=1~n 。
在分配任务i 时，只有2种情形，x i =1或x i =0。
此时，令S(i)={S(i-1)+(a i,0,2i)}U{S(i-1)+(0,b i,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即为所求的最优解，其最优值为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,1,0,1）因此，F=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), (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<iostream>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;//===========数组初始化===================for(i = 0; i <= mn; i++)for(j = 0; j <= mn; j++){ p[i][j][0] = true;for(k = 1 ; k <= n; k++)p[i][j][k] = false;}//===========动态递归=============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]) >= 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;}}return 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;//=========动态规划求解=================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); 由于求解过程比较繁锁,这里只说个大概算法执行过程,首先,用p[i][j][k],记录下对于第k 个作业,能否在对于a机器是i时间以,对于b机器是j时间以完成,如果能,则把p[i][j][k]设为true.经过了设置后,求对于n个作业的所有可能的值为p[i][j][n],对min(max(i,j)),结果为15.即为所得到的结果.3．考虑下面特殊的整数线性规划问题ni x b xa x c i ni iini ii 1},2,1,0{,max 11试设计一个解此问题的动态规划算法，并分析算法的时间复杂度。
