文档介绍：搜索算法例题讲解史宁西安电子科技大学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)