B5-搜索与回溯算法.ppt

搜索与回溯算法——例9 搜索与回溯算法——例9 #includeiostream using namespace std; int n,k; int f(int a,int b,int c) { int g=0,i; if (b==1) //递归边界，只划分1份 g=1; else for (i=c;i=a/b;i++) //第一个数的取值为c~a/b g+=f(a-i,b-1,i); //未划分的数有a-i，需划分为b-1份，每份最小为i return g; } int main() { cin n k; coutf(n,k,1); return 0; } 时间复杂度： 　　由于在搜索每一位数字的数值时做到了①保证有解②没有重复，整个搜索过程没有无用或重复的搜索分支，因此时间复杂度跟本题的答案是同一个数量级别。答案的数量级别估算如下： 　　1、不排除重复，把n分为k份，有C(n-1,k-1)种分法 　　2、n和k的数字越大，其中重复的比例越接近于A(k,k) 所以估计本题的时间复杂度为O(C(n-1,k-1)/k!) 　　当n=200，k=6时，时间复杂度为10^6 搜索与回溯算法——例9 【算法分析3——动态循环枚举】 回到第一种思路，枚举出所有组合，然后逐一判断组合是否满足条件。在数据规模较大时，将因为组合数量很大而超时。事实上，绝大部分的组合是不满足条件的，如果能减少或不枚举不满足条件的组合，那么将极大地节省运行时间，这在搜索中称为剪枝。 以n=7，k=3为例： 第1个数的枚举范围为1~2 第2个数的枚举范围根据第1个数动态调整 ①1 × ×：剩余6，第2个数的枚举范围为1~3 ②2 × ×：剩余5，第2个数的枚举范围为2~2 第3个数即最后1个数必须等于剩余的数，不需枚举 假设在枚举第dep个数时，还剩余rest，第det-1个数为last， 若depk，则第i个数的枚举范围是last~rest/(k-dep+1) 若dep=k，则第i个数等于rest，得到一个满足条件的组合 搜索与回溯算法——例9 #includeiostream using namespace std; int n,k,total; void select(int dep,int rest,int last) { int i; if (dep==k) //最后1个数只能等于rest，不需枚举，得到一个解 total++; else for (i=last;i=rest/(k-dep+1);i++) //枚举第dep个数 select(dep+1,rest-i,i); //递归枚举下一个数 } int main() { cin nk; total=0; select(1,n,1); //从第一个数开始枚举 couttotal; return 0; } 时间复杂度参照上一个解法 上机练习 1、全排列问题：输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。 2、组合的输出：排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。 现要求你用递归的方法输出所有组合。 3、N皇后问题：在N*N的棋盘上放置N个皇后（n=10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。 4、有重复元素的排列问题：设R={r1,r2,…,rn}是要进行排列的n个元素。其中元素r1,r2,…,rn可能相同。试设计一个算法，列出R的所有不同排列的总数。 上机练习 5、子集和问题：对于给定的正整数的集合S={x1，x2，…，xn}和正整数c，判定是否存在S的一个子集S，使得子集S所有元素的和等于c。 6、工作分配问题：设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。 7、装载问题：有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。 8、字符序列：从三个元素的集合[A，B，C]中选取元素生成一个N个字符组成的序列，使得没有两个相邻字的子序列（子序列长度=2）相同。例：N=5时ABCBA是合格的，而序列ABCBC与ABABC是不合格的，因为其中子序列BC，AB是相同的。求出满足条件的N (1=N=12)个字符的所有序列总数。 上机练习 9、迷宫问题：设