《第5章回溯法习题课件复习课程》由会员分享，可在线阅读，更多相关《第5章回溯法习题课件复习课程（5页珍藏版）》请在金锄头文库上搜索。
1、第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 sol
2、ution!”。 输入示例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运动员最佳匹配问题
3、问题描述羽毛球队有男女运动员各n人。 给定2个nn矩阵P和Q。 Pij是男运动员i和和女运动员j配对组成混合双打的男运动员竞赛优势；Qij是女运动员i和男运动员j配合的女运动员竞赛优势。 由于技术配合和心理状态等各种因素影响，Pij不一定等于Qji。 男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为Pij*Qji。 设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。 10运动员最佳匹配问题编程任务设计一个算法，对于给定的男女运动员竞赛优势，计算男女运。 动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。 数据输入第一行有1个正整数n(1n20)。 接下
4、来的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);/将结
5、点还回去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();。 内容仅供参考
