《回溯法习题》ppt课件

《《回溯法习题》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程安排12345678910111213141516周二PPTTPTTPTTPTTTTP周四PPPPPPPPPPPPPP端午考试T1第5章回溯法习题课第5章回溯法习题子集和问题最小长度电路板排列问题最小重量机器设计问题运动员最佳匹配问题无分隔符字典问题无和集问题n色方柱问题整数变换问题拉丁矩阵问题排列宝石问题重复拉丁矩阵问题罗密欧与朱丽叶的迷宫问题工作分配问题独立钻石跳棋问题智力拼图问题布线问题最佳调度问题无优先级运算问题世界名画陈列馆问题世界名画陈列馆问题（不重复监视）魔方问题魔方(Rubik’sCube)问题算24点问题算m点问题双轨车皮编序问

2、题多轨车皮编序问题部落卫队问题虫蚀算式问题完备环序列问题离散01串问题喷漆机器人问题子集树问题0-1背包问题排列树问题一般解空间搜索问题最短加法链问题n2-1谜问题3第5章回溯法习题子集和问题运动员最佳匹配问题最佳调度问题离散01串问题4子集和问题的一个实例为〈S,t〉。其中，S={x1,x2,…,xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得试设计一个解子集和问题的回溯法。编程任务：对于给定的正整数的集合S={x1,x2,…,xn}和正整数c，编程计算S的一个子集S1，使得5-1子集和问题5子集和问题数据输入

3、：第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。结果输出：输出子集和问题的解。当问题无解时，输出“Nosolution!”。输入示例51022654输出示例2266子集和问题算法类似于装载问题boolSubsum::backtrack(inti){//从1开始调用if(i>n){//计算完毕for(intj=1;j<=n;j++)bestx[j]=x[j];//记录最优解bestw=cw;if(bestw==c)returntrue;//满足条件(找到了)elsereturnfalse

4、;}7子集和问题算法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;}85-4运动员最佳匹配问题问题描述：羽毛球队有男女运动员各n人。给定2个n×n矩阵P和Q。P[i][j]是男运动

5、员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。9运动员最佳匹配问题编程任务：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。数据输入：第一行有1个正整数n(1≤n≤20)。接下来的2

6、n行，每行n个数。前n行是p，后n行是q。结果输出:男女双方竞赛优势的总和的最大值。输入示例：31023234345222353451输出示例：52pq10运动员最佳匹配问题结果输出:男女双方竞赛优势的总和的最大值。样例分析输入示例：31023234345222353451输出示例：52pq123132r10*2+4*5+4*3=52for(inti=1,temp=0;i<=n;i++)temp+=p[i][r[i]]*q[r[i]][i];只有一个下标是变化的11运动员最佳匹配问题算法解空间是一棵排列树voidpref::Backtrack(int

7、t){//从1开始回溯if(t>n)Compute();//构成1次全排列elsefor(intj=t;j<=n;j++){//从结点t到叶结点swap(r[t],r[j]);//将结点j作为当前结点Backtrack(t+1);swap(r[t],r[j]);//将结点还回去}}12运动员最佳匹配问题算法voidpref::Compute(void){//计算当前排列的竞赛优势for(inti=1,temp=0;i<=n;i++)//按题目要求计算temp+=p[i][r[i]]*q[r[i]][i];if(temp>best){//是更好的值？b

8、est=temp;for(inti=1;i<=n;i++)//构造最优解bestr[i]=r[i];}}13