资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
第5章回溯法习题课件复习课程 1课程安排12345678910111213141516周二P P P PT T T TP PT T T TP PT T T TP PT T TTTTTTP P周四P P P P P P P P P P P P P PPPPPPPPPPPPPPP端午考试TT2第55章回溯法习题课4第55章回溯法习题1.子集和问题2.运动员最佳匹配问题3.最佳调度问题4.离散01串问题6子集和问题数据输入第第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值。 接下来的1行中,有n个正整数,表示集合S中的元素。 结果输出输出子集和问题的解。 当问题无解时,输出“No solution!”。 输入示例51022654输出示例2267子集和问题算法类似于装载问题bool Subsum:backtrack(int i)/从1开始调用if(in)/计算完毕for(int j=1;j=n;j+)bestxj=xj;/记录最优解bestw=cw;if(bestw=c)return true;/满足条件(找到了)else return false;8子集和问题算法r-=wi;/剩余大小if(cw+wibestw)/上界函数xi=0;/右子树if(backtrack(i+1)return true;r+=wi;/右子树无最优解return false;95-4运动员最佳匹配问题问题描述羽毛球队有男女运动员各n人。 给定2个nn矩阵P和Q。 Pij是男运动员i和和女运动员j配对组成混合双打的男运动员竞赛优势;Qij是女运动员i和男运动员j配合的女运动员竞赛优势。 由于技术配合和心理状态等各种因素影响,Pij不一定等于Qji。 男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为Pij*Qji。 设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。 10运动员最佳匹配问题编程任务设计一个算法,对于给定的男女运动员竞赛优势,计算男女运。 动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。 数据输入第一行有1个正整数n(1n20)。 接下来的2n行,每行n个数。 前前n行是p,后n行是q。 结果输出:男女双方竞赛优势的总和的最大值。 输入示例31023234345222353451输出示例52p q11运动员最佳匹配问题结果输出:男女双方竞赛优势的总和的最大值。 样例分析输入示例31023234345222353451输出示例52p q123132r10*2+4*5+4*3=52for(int i=1,temp=0;in)Compute();/构成1次全排列else for(int j=t;j=n;j+)/从结点t到叶结点swap(rt,rj);/将结点j作为当前结点Backtrack(t+1);swap(rt,rj);/将结点还回去13运动员最佳匹配问题算法void pref:Compute(void)/计算当前排列的竞赛优势for(int i=1,temp=0;ibest)/是更好的值?best=temp;for(int i=1;in)/一种情况构造完毕tot+=2;/个数加倍return;for(int i=0;i2;i+)bstrlev=i;/0,1/满足条件就回溯if(bstrok(lev)backtrack(lev+1);235-30离散01串问题bool bstrok(int lev)/第lev位for(int i=0;i0)/下标必须大于0if(same()return false;/是相同的for(int i=0;iusing namespacestd;int n,k;int tot;short*bstr;int*x;bool bstrok(int lev);bool same();。 内容仅供参考
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号