部分选题目录
课后习题四课后习题六课后习题七课后习题八课后习题九课后习题四
8、设计分治算法求解一维空间上n个点的最近对问题
（1） 分治法求解：
MinDistance(P,X,Y)
输入：P为n个点的集合，X、Y分别是横坐标和纵坐标的数组
输出：两个点的距离
1、 如果P中点数等于2，直接计算距离。
2、 如果P中点数等于3，计算距离两两比较获得最短距离。
3、 分别对X、Y排序。
4、 做垂线l将P划分为P1、P2，P1为左边的点，P2为右边的点
5、 MinDistance（P1，X1，Y1）；leftMin=P1中的最小距离。
6、 MinDistance（P2，X2，X3）；rightMin=P2中的最小距离。
7、 minD=min（leftMin，rightMin）；
8、 检查距l不超过minD两侧各一个点的距离，若小于minD，修改minD为这个值。
（2） 时间复杂度分析
第1、2步：O（1）第3步：O（nlogn）
第4步：O（1） 第5、6步：2T（n/2）
第7步：O（1） 第8步：O（n）
所以：
n<=3时：T（n）=O（1）
T（n）=2T（n/2）+O（nlogn）=O（nlog2n）
课后习题六
3、用动态规划法求如下0/1背包问题的最优解：有5个物品，其重量分别为（3,2,1,4,5），价值分别为（25,20,15,40,50），背包容量为6。写出求解过程。
（1） 动态规划法求解：
KnapScak（w，v，x，n）
输入：w[5]、v[5]分别为存放5个物品的重量和价值的数组，最终的5个物品是否装入情况存放在数组x[5]中。
输出：vl[5][6]为物品数为5、背包容量为6时的最大价值二维数组元素
1、 将vl[i][0]置为0，i=0,1,2,…,n
2、 将vl[0][j]置为0，i=0,1,2,…,n
3、 若第i个物品重量j小于等于6，则如果第i个物品没有装入背包，背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值vl[i][j]=vl[i-1][j]；反则如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi。取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。
4、 当前i种物品装入容量为j的背包中所取得的价值大于前i-1种物品装入容量为j的背包中所取得的价值时，x[i]=1，j=j-w[i-1]，否则x[i]=0
（2） 时间复杂度分析
第1、2步：O（n）
第3步：O（nm）（其中m=C）
第4步：O（n）
所以：W（n）=O（nm）
课后习题七
6、设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti（1<=i<=n），应如何安排n个顾客的服务次序才能使顾客总的等待时间达到最小？
（1） 贪心法求解：
MinTime（t,n）
输入：n为顾客的数目，t[n]为顾客i需要的服务时间ti
输出：总的等待时间sum
1、 对t[n]从小到大排序
2、 总等待时间sum置0
3、 i从1到n，t[i]+=t[i-1],sum+=t[i]；
（2） 时间复杂度分析：
第1步：O（n2）最坏情况
第2步：O（1）
第3步：O（n）
所以：W（n）=O（n2）
课后习题八
3、有三个作业{1,2,3}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，这三个作业在机器1上所需要的处理时间为（2,3,2），在机器2上所需要的处理时间为（1,1,3），用回溯法求解这三个作业完成的最短时间，画出搜索空间。
（1） 回溯法求解：
traceback（t）
输入：作业数3，第i台机器上作业j的调度m[j][i]
输出：完成三个作业的最短时间bestf
1、 如果作业数小于t，即达到叶子结点，当前调度为最佳调度bestx[i]=x[i]，更新最小时间和bestf=cf，i=1,2，…，n
2、 若未到达叶子结点，先向下一层探索，记录作业在机器1运行的时间f1+=m[x[j]][1]，且保存上一个作业在机器2完成的时间；记录当前作业在机器2完成的时间f2=（f1>f2？f1：f2）+m[x[j]][2],且记录当前在机器2上完成的时间和cf+=f2；若cf小于bestf，交换两个作业的位置，traceback（t+1）后再次交换两个作业的位置；
最后回溯到父结点，即f1-=m[x[j]][1]；cf-=f2，并将保存的上一个作业处理时间置为f2。其中j=t，t+1,…，n
（2） 时间复杂度分析：
第1步：O(n)
第2步：O（n！）
所以：W（n）=O（n！）
课后习题九
9、设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得，设Wij是从供应商j处购得的部件i的重量，Cij是相应的价格。设计分支限界算法，给出总价格不超过d的最小重量机器设计。
（1） 分支限界法求解：
MinWeight（C，W，m，n，d）
输入：供应商j处购得的部件i的价格C[i][j]，供应商j处购得的部件i的重量W[i][j]，机器部件数量n，供应商数量m，总价格d
输出：最小重量minWeight
1、 初始化一个为0的结点，放入优先队列
2、 当队列不为空时：当取出节点到达叶子节点，如果所找到的这条路径的零件总重量小于之前的重量minWeight，则更新最小重量minWeight和最小价值minValue；
3、 当队列不为空时：当取出节点未到达叶子节点，遍历该节点到叶子节点后面的最优路径的所有节点，并选取每一层中重量最小和价值最小的节点进行最小值累加；如果当前价格最小值大于d或当前重量最小值大于该节点到最终叶子节点中所有节点重量最小值，即minWeight，则将剩下节点置为死节点；
4、 当队列不为空时：最后遍历m，将剩下符合要求的所有节点放入优先队列中。
（2） 时间复杂度分析：
第1步：O（1）
第2步：O（n）
第3步：O（nm）
第4步：O（m）
所以：W（n）=O（nm）
注：以上为个人解答过程，有错可以指出。
