题目:埃及分数
题目链接:http://codevs.cn/problem/1288/
题目大意:
给出一个分数,由分子a 和分母b 构成,现在要你分解成一系列互不相同的单位分数(形如:1/a,即分子为1),要求:分解成的单位分数数量越少越好,如果数量一样,最小的那个单位分数越大越好。
如:
19/45 = 1/3 + 1/12 + 1/180;
19/45 = 1/5 + 1/6 + 1/18;
以上两种分解方法都要3个单位分数,但下面一个的最小单位分数1/18比上一个1/180大,所以第二个更优。
思路:
虽然是求最优解,但这道明显不是广搜吧(空间要求太高),而且很明显是用深搜做,即从1~无穷,每一个分母,都有选中和不选中两种状态,如果选中,那么就减去这个分数,没有就是跳过,但无穷到底是哪里呢,而且具体要选几个呢,这就是这道题的难点。因为多组答案的优先级是由单位分数的个数首先决定,那么我们可以逐次放宽个数的限制,即迭代加深搜索。
迭代加深搜索的具体内容:第一次,我限制只能用k个单位分数来完成,如果找完所有情况,还是没找到解,那么我现在用k+1个单位分数解决,这样优点如下:
1. 肯定保证最优解,因为我用k个来完成分解就说明比k小的个数分解不出来,如果分解得出来,我在那时就退出循环了。
2. 虽然看似重复进行了很多遍的搜索,但上一层的搜索量和下一层比起来太少了,不影响总的时间复杂度。
抛开逐步解开个数限制外,每一个个数限制下的做法和平常的深入优先搜索大致相同,要注意剪枝!
主要的两个剪枝如下:
1. 限制开头:并不是每次都要从1开始遍历分母,假设现在要分解a/b,那么分母b/a就是起点,因为b/a的分数太大,起始点已经超过了a/b,没有什么意义:1/(b/a)=a/b ,假设起点s<b/a,那么显而易见,起点的分数已经比我们要的总和(a/b)大了。
2. 限制结尾:
(1)比较简单的限制结尾可以这样看:如果我已经找到分母k了,而现在要分解得分数是a/b,现在还要找m个单位分数,那么可以想象:有可能 m * ( 1/k ) 还小于a/b,也就是说就算全是1/k,我凑够m个,也达不到a/b,那么说明前面的分配方案肯定有无,直接可以return了。加上这个剪枝已经可以得到答案了,只是时间有点慢罢了。
(2)现在我们假设终点为t,还要找m个单位分数,现在的分数剩下a/b,那么很容易有m * (1/t) <= a / b ,也就是说我如果m个都用最小的,肯定小于等于a/b。(等于号就是说有可能m=1,我可能直接终点就是答案,如果m>1,那么终点肯定也不可能选到,假设选了(后面还要选(m-1)个,肯定凑不够)这样子,由上面的式子,经过变换,可以得到 t >= m*b/a ,也就是说终点为m*b/a。
有了思路代码还是很容易的:
1 #include2 #include 3 #include 4 5 int gcd(int a,int b) 6 { 7 return b?gcd(b,a%b):a; 8 } 9 10 int ans[1000],ao;11 int out[1000],oo;12 13 void dfs(int limit,int h,int ma,int mb)14 {15 if(h==limit) return ;16 if(mb%ma==0 && mb/ma>ans[ao-1] && ( oo<=0 || mb/ma < out[oo-1] ))17 {18 ans[ao++]=mb/ma;19 oo=ao;20 memcpy(out,ans,sizeof(ans));21 ao--;22 return ;23 }24 int i=mb/ma-1;25 if(i<=ans[ao-1]) i=ans[ao-1]; //ans[ao-1]就是前面找过的最后一个,这前面的都处理过(选中or不选中)26 int j=(limit-h)*mb/ma;27 while(++i<=j)28 {29 if(oo>0&&i>=out[oo-1]) return ;30 int g=gcd(i,mb);31 int k=i/g;32 //if(ma*i/mb+h>limit) return ;33 int x=mb*k;34 int y=ma*k-mb/g;35 if(y<0) continue;36 ans[ao++]=i;37 if(y==0)38 {39 oo=ao;40 memcpy(out,ans,sizeof(ans));41 ao--;42 return ;43 }44 dfs(limit,h+1,y,x);45 ao--;46 }47 }48 49 int main()50 {51 int a,b;52 while(scanf("%d%d",&a,&b)!=EOF)53 {54 ao=0;55 oo=0;56 for(int i=1;i<100;i++)57 {58 //printf("%d\n",i);59 dfs(i,0,a,b);60 if(oo>0) break;61 }62 for(int i=0;i