第5章回溯法习题讲义

第5章回溯法习题讲义第5章回溯法习题课3第5章回溯法习题子集和问题最小长度电路板排列问题最小重量机器设计问题运动员最佳匹配问题无分隔符字典问题无和集问题n色方柱问题整数变换问题拉丁矩阵问题排列宝石问题重复拉丁矩阵问题罗密欧与朱丽叶的迷宫问题工作分配问题独立钻石跳棋问题智力拼图问题布线问题最佳调度问题无优先级运算问题世界名画陈列馆问题世界名画陈列馆问题（不重复监视）魔方问题魔方(Rubik’sCube)问题算24点问题算m点问题双轨车皮编序问题多轨车皮编序问题部落卫队问题虫蚀算式问题完备环序列问题离散01串问题喷漆机器人问题子集树问题0-1背包问题排列树问题一般解空间搜索问题最短加法链问题n2-1谜问题4第5章回溯法习题子集和问题运动员最佳匹配问题最佳调度问题离散01串问题5子集和问题的一个实例为〈S,t〉。其中，S={x1,x2,…,xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得 试设计一个解子集和问题的回溯法。编程任务：

对于给定的正整数的集合S={x1,x2,…,xn}和正整数c，编程计算S的一个子集S1，使得5-1子集和问题6子集和问题数据输入： 第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。结果输出： 输出子集和问题的解。当问题无解时，输出“Nosolution!”。输入示例 510 22654输出示例 2267子集和问题算法类似于装载问题boolSubsum::backtrack(inti){ //从1开始调用 if(i>n){ //计算完毕 for(intj=1;j<=n;j++) bestx[j]=x[j]; //记录最优解 bestw=cw; if(bestw==c)returntrue; //满足条件(找到了) elsereturnfalse; }8子集和问题算法

r-=w[i]; //剩余大小 if(cw+w[i]<=c){ //第i个数可以使用 x[i]=1; //左子树 cw+=w[i]; //当前和加上w[i] if(backtrack(i+1))returntrue; cw-=w[i]; //准备进入右子树 } if(cw+r>bestw){//上界函数 x[i]=0; //右子树 if(backtrack(i+1))returntrue; } r+=w[i]; //右子树无最优解

returnfalse;}95-4运动员最佳匹配问题问题描述：羽毛球队有男女运动员各n人。给定2个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。10运动员最佳匹配问题编程任务： 设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。数据输入： 第一行有1个正整数n(1≤n≤20)。接下来的2n行，每行n个数。前n行是p，后n行是q。结果输出: 男女双方竞赛优势的总和的最大值。输入示例：31023234345222353451输出示例：52pq11运动员最佳匹配问题结果输出: 男女双方竞赛优势的总和的最大值。样例分析输入示例：31023234345222353451输出示例：52pq123132r10*2+4*5+4*3=52for(inti=1,temp=0;i<=n;i++) temp+=p[i][r[i]]*q[r[i]][i];只有一个下标是变化的12运动员最佳匹配问题算法解空间是一棵排列树voidpref::Backtrack(intt){ //从1开始回溯 if(t>n)Compute(); //构成1次全排列 else for(intj=t;j<=n;j++){ //从结点t到叶结点 swap(r[t],r[j]); //将结点j作为当前结点 Backtrack(t+1); swap(r[t],r[j]); //将结点还回去 }}13运动员最佳匹配问题算法voidpref::Compute(void){ //计算当前排列的竞赛优势 for(inti=1,temp=0;i<=n;i++) //按题目要求计算 temp+=p[i][r[i]]*q[r[i]][i]; if(temp>best){ //是更好的值？ best=temp; for(inti=1;i<=n;i++) //构造最优解 bestr[i]=r[i]; }}14运动员最佳匹配问题算法15运动员最佳匹配问题算法main()中的前半部分：165-17最佳调度问题 假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。编程任务： 对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1~n。编程计算完成这n个任务的最佳调度。17最佳调度问题数据输入： 第一行有2个正整数n和k。第2行的n个正整数是完成n个任务需要的时间。结果输出: 完成全部任务的最早时间。输入示例73214416653输出示例17184.7多机调度问题按算法greedy产生的作业调度如下图所示，所需的加工时间为17。最长处理时间作业优先,机器空闲时间最长优先安排19最佳调度问题算法voidsearch(intdep){ //初值为1 if(dep==n){ //形成一种调度方案 inttemp=comp(); //计算完成任务的时间 if(tmp<best)best=tmp; //更新最优解 return; } for(inti=0;i<k;i++){ //对每台机器回溯 len[i]+=t[dep]; //安排任务dep(左子树) if(len[i]<best)search(dep+1); len[i]-=t[dep]; //右子树

}}20最佳调度问题算法计算完成任务的时间intcomp(){ inttmp=0; //在k台机器中查找最大值 for(inti=0;i<k;i++) if(len[i]>tmp)tmp=len[i]; returntmp;}215-30离散01串问题

(n,k)01串定义为：长度为n的01串，其中不含k个连续的相同子串。对于给定的正整数n和k，计算(n,k)01串的个数。编程任务：对于给定的正整数n和k，计算(n,k)01串的个数。数据输入： 第一行有2个正整数n和k，1≤k，n≤40。结果输出:(n,k)01串的个数。输入示例23输出示例43 3 → 63 → 103 → 16225-30离散01串问题

具有对称性，只要考察首字符为0的情况，将找到的符合条件的0-1串的个数加倍。voidbacktrack(intlev){ //lev从2开始 if(lev>n){ //一种情况构造完毕 tot+=2; //个数加倍 return; } for(inti=0;i<2;i++){ bstr[lev]=i; //0，1 //满足条件就回溯 if(bstrok(lev))backtrack(lev+1); }}235-30离散01串问题

//判断是否相同boolsame(){ intlen=x[0]-x[1]; //计算位置差 for(inti=0;i<len;i++) //搜索每一位 for(intj=1;j<k;j++) //每次搜索k位 if(bstr[x[j]+i]!=bstr[x