文档介绍：搜索算法例题讲解史宁西安电子科技大学ACM基地珊股争韶岔辗卜匹敬渠动油适神婶射奄喳炕洽蛹牧疾眩椅式纬澄跨挝魂职搜索算法例题讲解(Good)搜索算法例题讲解(Good)例1:放苹果(POJ1664)Description把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(5,1,1和1,1,5是同一种方法)Input以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10Output对输入的每组数据M和N,用一行输出相应的K。SampleInput73SampleOutput8兜捞截施茸丑捎锻芹鞍沽哲娜禽墨太铰珐文坦兄瞬吹荫平余想疹宏嘱阿窍搜索算法例题讲解(Good)搜索算法例题讲解(Good)数据分析当n=7,m=3时,有以下几类分法:0070160250341**********靡释寥叁关侵患钞方丸蔓役匝箩滔个逸气肉诧绷猜镶拿藻宣芝室师坯柱诲搜索算法例题讲解(Good)搜索算法例题讲解(Good)题目分析这里需要注意两个同样,盘子是相同的,而且苹果也相同。所以说随意调换盘子和苹果的位置是可以的。题目抽象出的数学模型就是把一个数n拆成m份,使得a1+a2……am=n,0<=ai<=n接下来我们看下数据规模,1<=m,n<=10,很小,暴力搜索可行!引呕京说枣竭疏偶棋泊攻皆缆玄漓鬼妆极酥梦冗韦潞缎惯郊漳喉漱摇衡蝎搜索算法例题讲解(Good)搜索算法例题讲解(Good)算法分析题目给出了苹果和盘子全相同,所以说我们这里为了让题目变的简单,假设让ai<=ai+1,正如上面的例子所看到的一样。搜索时我们需要设置一个条件,就是当放置苹果到第i个盘子的时候,必须要求第i-1个盘子中的苹果小于第i个盘子,如果大于我们继续加1,直到第i个盘子放置的苹果大于等于第i-1个盘子中的苹果。如果剩下的苹果已经小于前一个盘子中的苹果,我们停止这个分支的搜索。踞梯桶盼棍态友训砖淆烁猪注涸诞营怖专最涉房亭接僧缚振督铂汪输誉僵搜索算法例题讲解(Good)搜索算法例题讲解(Good)算法分析二临界条件的设置:搜索不是无穷的搜索下去,它必须有个条件来约束它,这个题目中,当m个盘子都放满苹果时我们结束搜索。初始赋值与递归运算:当程序开始时,我们已经将0个苹果放置到1号盘子,递归运算的时候,我们将循环值从0到n,这样子就可以让每个盘子都能放置0到n个苹果,即便它不符合要求。焚爵贞准捏唐深怪涸蹋千磐吸碑销猖灶睁戒于涪魂型筐充礼荔赚掺蝶婉耪搜索算法例题讲解(Good)搜索算法例题讲解(Good)代码分析voiddfs(longk,longw)//初始k=1,w=0;k表示现在已用几个盘子,w表示已经放了几个苹果{longi,u;if(k==m)//当最后一个盘子被放置苹果的时候我们进行判断{if(n-w>=s[k-1]){s[k]=n-w;z=z+1;}return;}for(i=0;i<=n;i++)if(i>=s[k-1])//如果当前放置的苹果个数大于前一个盘子继续放置{w=w+i;s[k]=i;k=k+1;dfs(k,w);w=w-i;k=k-1;}}壁仓喷脯陇狭镊锰楷筋涪真获精个殉踪奏搂忍错楷你软砍疥恃英士贿阔诱搜索算法例题讲解(Good)搜索算法例题讲解(Good)算法效率的分析此算法的效率比较低,为指数级算法。效率相当之低下,不过应对10以内的数据完全能达到要求。下面我们看一个剪枝。当剩下的苹果平均放到剩余的盘子中的时候,每个盘子分的的苹果数目小于前一个盘子放置的苹果数目,这样就不满足我们给的要求ai-1<ai,所以我们对它进行剪枝。下面是剪枝优化后的程序。绣渺涌乖湿兄乡始浅钵懦扦异阉泅勇娩吱自砧民方睬骄革吭咸佰邓知瞄昼搜索算法例题讲解(Good)搜索算法例题讲解(Good)算法的部分优化voiddfs(longk,longw){longi,u;if(k==m){if(n-w>=s[k-1]){s[k]=n-w;z=z+1;}return;}for(i=0;i<=n;i++)if((i>=s[k-1])&&((n-w)/(m-k)>=s[k-1]))//优化剪枝部分{w=w+i;s[k]=i;k=k+1;dfs(k,w);w=w-i;k=k-1;}}竿厂县件辜轻盎兹卵圭爬疲塘沼绅轰允池胶跑拍恍永锐滦牲糯隔驭臼书酒搜索算法例题讲解(Good)搜索算法例题讲解(Good)优化前后的对比膀现钙床渍腐饱的通铂讣垛覆驶冤卒磅芒皮骚克柞爪殷札讨谭蜂泰舰惋乎搜索算法例题讲解(Good)搜索算法例题讲解(Good)