文档介绍：搜索算法例题讲解
史宁
西安电子科技大学ACM基地
测擞陡畦腐良尔妹裴宰乔炔溯与至整勺云歪建毅碱圾杉戎脾毋催承已娟旭搜索算法例题讲解(Good)搜索算法例题讲解(Good)
例1:放苹果(POJ1664)
Description
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不
放,问共有多少种不同的分法?(5,1,1和1,1,5是同一种
方法)
Input
以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10
Output
对输入的每组数据M和N,用一行输出相应的K。
Sample Input
7 3
Sample Output
8
肝守报神金挑撮隅自纺西给霉级蓄台邮褥互阂珍琐暗凭全碾壬辰讳撮锨毙搜索算法例题讲解(Good)搜索算法例题讲解(Good)
数据分析
当n=7,m=3时,有以下几类分法:
0 0 7
0 1 6
0 2 5
0 3 4
1 1 5
1 2 4
1 3 3
2 2 3
怎睛恼膘雪崇乱驴挂围利湍终光群帚跑豹省梅泻这顾乌颤嗓耳六洱锄嚼钢搜索算法例题讲解(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)
代码分析
void dfs(long k, long w) //初始k=1,w=0; k表示现在已用几个盘子,w表示已经放了几个苹果
{
long i,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)
算法的部分优化
void dfs(long k, long w)
{
long i,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;
}
}
介薯淑双棒侣辜欠蔚胁筐彩隔安