codevs1288 埃及分数问题 迭代加深

题目

给你一个真分数,问它最少能拆成几个单位分数的和,如果有多组解,选择最小分数最大的那组.

19/45=1/3 + 1/12 + 1/180

19/45=1/3 + 1/15 + 1/45

19/45=1/3 + 1/18 + 1/30,

19/45=1/4 + 1/6 + 1/180

19/45=1/5 + 1/6 + 1/18

所以最后答案为5,6,18.

题解

早就听说了IDA*,一直没学.

这个算是第一道IDA*题.

IDA*给我的感觉就是每次限制了搜索层数的dfs,先搜索第i层,如果没有解,那么就继续搜索第i+1层,这样一直做下去.这个的感觉有点像bfs,但是它省空间啊.

随着深度增加,搜索空间的大小指数增加,IDA*在递归深度限制的过程中虽然重复搜索了很多状态,但总的访问状态数和最后一次所访问的状态数还是同一数量级的.

IDA*适用于搜索树很大,但答案所在深度不深的题目

大体框架就是:

int  res=0;
while(dfs(0,0,res)==INF)res++;
printf("%d\n",res);

我们让分母值单调增加,对于这个题的一个减枝就是,如果使用cnt个单位分数让他们的值$\ge \frac{a}{b}$,那么 $\frac{cnt}{x} \geq \frac{a}{b}$

那么$x \leq \frac{cnt\times b}{a}$

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e9+7;
int a,b,tot;
bool hasAns;
LL gcd(LL a,LL b){
	return b?gcd(b,a%b):a;
}
LL ans[100],res[100];
LL minFenmu;
void  dfs(int now,int dep,LL fenzi,LL fenmu,LL prev){//prev单调递增
	if(now>=dep)return ;
	LL limit=max(fenmu/fenzi,prev+1);
	for(LL i=limit;i<=ceil((double)fenmu*(dep-now)/fenzi);++i){
		if(i>minFenmu)return ;
		if(fenmu>i*fenzi)continue;
		else if(fenmu==i*fenzi){
			hasAns=true;
			ans[tot++]=i;
			if(i<res[tot-1]){
				for(int k=0;k<tot;++k){
					res[k]=ans[k];
				}
			}
			minFenmu=min(minFenmu,i);//已经得到的解的最小分母的值,用于剪枝
			--tot;
			return ;
		}else{
			LL aa=fenzi*i-fenmu;
			LL bb=fenmu*i;
			LL GCD=gcd(aa,bb);
			ans[tot++]=i;
			dfs(now+1,dep,aa/GCD,bb/GCD,i);
			tot--;//回溯
		}
	}
	return ;
}
int main(){
	scanf("%d%d",&a,&b);
	int k=1;
	hasAns=false;
	tot=0;
	minFenmu=INF;
	for(int i=0;i<100;++i)res[i]=INF;
	for(;;){
		dfs(0,k,a,b,0);
		if(hasAns){
			break;
		}
		k++;
	}
	for(int i=0;i<k;++i){
		printf("%lld ",res[i]);
	}
	printf("\n");
	return 0;
}