第5章回溯法习题ppt课件.ppt

《第5章回溯法习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《第5章回溯法习题ppt课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章回溯法习题ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第第5 5章章 回溯法习题课回溯法习题课2第第5 5章章 回溯法习题回溯法习题1.子集和问题子集和问题2.运动员最佳匹配问题运动员最佳匹配问题3.最佳调度问题最佳调度问题4.离散离散01串问题串问题4子集和问题的一个实例为子集和问题的一个实例为S,t。其中，。其中，S=x1,x2,xn 是一个正整数的集合是一个正整数的集合，c是一个正整数。是一个正整数。子集和问题判定是否存在子集和问题判定是

2、否存在S 的一个子集的一个子集S1，使得，使得试设计一个解子集和问题的回溯法。试设计一个解子集和问题的回溯法。编编程任程任务务：对于给定的正整数的集合对于给定的正整数的集合S=x1,x2,xn和正整数和正整数c，编，编程计算程计算S 的一个子集的一个子集S1，使得，使得5-1 子集和问题子集和问题5子集和问题子集和问题数据输入：数据输入：第第1行有行有2个正整数个正整数n和和c，n表示表示S的大小，的大小，c是子集是子集和的目标值。接下来的和的目标值。接下来的1 行中，有行中，有n个正整数，表示个正整数，表示集合集合S 中的元素。中的元素。结果输出：结果输出：输出子集和问题的解。当问题无解时，

3、输出输出子集和问题的解。当问题无解时，输出“No solution!”。输入示例输入示例5 102 2 6 5 4 输出示例输出示例2 2 66子集和问题算法子集和问题算法类似于类似于装载问题装载问题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;7子集和问题算法子集和问题算法r-=wi;/剩余大小剩余大小if(cw+wi

4、bestw)/上界函数上界函数xi=0;/右子树右子树if(backtrack(i+1)return true;r+=wi;/右子树无最优解右子树无最优解return false;85-4 运动员最佳匹配问题运动员最佳匹配问题问题描述：问题描述：羽毛球队有男女运动员各羽毛球队有男女运动员各n 人。人。给定给定2 个个nn 矩阵矩阵P 和和Q。Pij 是男运动员是男运动员i 和女和女运动员运动员j 配对组成混合双打的男运动员竞赛优势；配对组成混合双打的男运动员竞赛优势；Qij 是女运动员是女运动员i 和男运动员和男运动员j 配合的女运动员竞配合的女运动员竞赛优势。赛优势。由于技术配合和心理状态等

5、各种因素影响，由于技术配合和心理状态等各种因素影响，Pij 不一定等于不一定等于Qji。男运动员男运动员i 和女运动员和女运动员j 配对组成混合双打的男女双配对组成混合双打的男女双方竞赛优势为方竞赛优势为Pij*Qji。设计一个算法，计算男女运动员最佳配对法，使各设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。组男女双方竞赛优势的总和达到最大。9运动员最佳匹配问题运动员最佳匹配问题编程任务：编程任务：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。动员

6、最佳配对法，使各组男女双方竞赛优势的总和达到最大。数据输入：数据输入：第一行有第一行有1 个正整数个正整数n(1n20)。接下来的。接下来的2n 行，每行行，每行n 个数。个数。前前n 行是行是p，后，后n 行是行是q。结果输出结果输出:男女双方竞赛优势的总和的最大值。男女双方竞赛优势的总和的最大值。输入示例：输入示例：310 2 3 2 3 4 3 4 5 2 2 2 3 5 3 4 5 1输出示例：输出示例：52pq10运动员最佳匹配问题运动员最佳匹配问题结果输出结果输出:男女双方竞赛优势的总和的最大值。男女双方竞赛优势的总和的最大值。样例分析样例分析输入示例：输入示例：310 2 3 2

7、 3 4 3 4 5 2 2 2 3 5 3 4 5 1输出示例：输出示例：52pq123132r10*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);/将结点还回去将结点还回去12运动员最佳匹配问题算法运动员最佳匹配问题算法void pref:Compute(void)/计算当前排列的竞赛优势计算当前排列的竞赛优势for(int

8、i=1,temp=0;ibest)/是更好的值？是更好的值？best=temp;for(int i=1;i=n;i+)/构造最优解构造最优解bestri=ri;13运动员最佳匹配问题算法运动员最佳匹配问题算法14运动员最佳匹配问题算法运动员最佳匹配问题算法main()中的前半部分：中的前半部分：155-17 最佳调度问题最佳调度问题假设有假设有n 个任务由个任务由k 个可并行工作的机器完成。完成个可并行工作的机器完成。完成任务任务i 需要的时间为需要的时间为ti。试设计一个算法找出完成这。试设计一个算法找出完成这n 个任务的最佳调度，使得完成全部任务的时间最早。个任务的最佳调度，使得完成全部任

9、务的时间最早。编程任务：编程任务：对任意给定的整数对任意给定的整数n 和和k，以及完成任务，以及完成任务i 需要的时间需要的时间为为ti，i=1n。编程计算完成这。编程计算完成这n个任务的最佳调度。个任务的最佳调度。16最佳调度问题最佳调度问题数据输入：数据输入：第一行有第一行有2 个正整数个正整数n 和和k。第。第2 行的行的n 个正整数是完个正整数是完成成n 个任务需要的时间。个任务需要的时间。结果输出结果输出:完成全部任务的最早时间。完成全部任务的最早时间。输入示例输入示例7 32 14 4 16 6 5 3输出示例输出示例17174.7 4.7 多机调度问题多机调度问题按算法按算法gr

10、eedy产生的作业调度如下图所示，所产生的作业调度如下图所示，所需的加工时间为需的加工时间为17。最长处理时间作业优先最长处理时间作业优先,机器空闲时间最长优先安排机器空闲时间最长优先安排18最佳调度问题算法最佳调度问题算法void search(int dep)/初值为初值为1if(dep=n)/形成一种调度方案形成一种调度方案int temp=comp();/计算完成任务的时间计算完成任务的时间if(tmpbest)best=tmp;/更新最优解更新最优解return;for(int i=0;ik;i+)/对每台机器回溯对每台机器回溯leni+=tdep;/安排任务安排任务dep(左子树左

11、子树)if(lenibest)search(dep+1);leni-=tdep;/右子树右子树19最佳调度问题算法最佳调度问题算法计算完成任务的时间计算完成任务的时间int comp()int tmp=0;/在在k台机器中查找最大值台机器中查找最大值for(int i=0;itmp)tmp=leni;return tmp;205-30 离散离散01串问题串问题(n,k)01 串定义为：长度为串定义为：长度为n 的的01 串，其中不含串，其中不含k 个连个连续的相同子串。对于给定的正整数续的相同子串。对于给定的正整数n 和和k，计算，计算(n,k)01 串的个数。串的个数。编程任务：编程任务：对

12、于给定的正整数对于给定的正整数n 和和k，计算，计算(n,k)01 串的个数。串的个数。数据输入：数据输入：第一行有第一行有2 个正整数个正整数n 和和k，1k，n40。结果输出结果输出:(n,k)01 串的个数。串的个数。输入示例输入示例2 3 输出示例输出示例433643105316215-30 离散离散01串问题串问题 具有对称性，只要考察首字符为具有对称性，只要考察首字符为0的情况，将找到的符的情况，将找到的符合条件的合条件的0-1串的个数加倍。串的个数加倍。void backtrack(int lev)/lev从从2开始开始if(levn)/一种情况构造完毕一种情况构造完毕tot+=

13、2;/个数加倍个数加倍return;for(int i=0;i2;i+)bstrlev=i;/0，1/满足条件就回溯满足条件就回溯if(bstrok(lev)backtrack(lev+1);225-30 离散离散01串问题串问题 bool bstrok(int lev)/第第lev位位for(int i=0;i0)/下标必须大于下标必须大于0if(same()return false;/是相同的是相同的for(int i=0;ik;i+)xi-=i+1;/每隔每隔i个位置个位置return true;235-30 离散离散01串问题串问题/判断是否相同判断是否相同bool same()int len=x0-x1;/计算位置差计算位置差for(int i=0;ilen;i+)/搜索每一位搜索每一位for(int j=1;jk;j+)/每次搜索每次搜索k位位if(bstrxj+i!=bstrxj-1+i)/相邻位相邻位return false;/只要有一个不相同即可只要有一个不相同即可return true;/相同相同245-30 离散离散01串问题串问题 文件头：文件头：#include using namespace std;int n,k;int tot;short*bstr;int*x;bool bstrok(int lev);bool same();25