ACM-搜索-回溯进阶迭代深搜IDA*---埃及分数

本文主要是介绍ACM-搜索-回溯进阶迭代深搜IDA*---埃及分数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写了。。。。两天
一开始看的时候就觉得不简单，后来看网上写的。。。越来越乱，后来比赛时翻书看到紫树上有。紫书P207,大家最好自己取翻翻看呀！
——————开始进入正题——————————–
题意：给出分子分母（保证真分数），求这个分数可以被1/n+1/m+….1/i表示，其中要求，这个式子的长度越短越好，这个式子的最小分数的分母越小越好，但是各个分母不能重复。即；

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. 
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。

输入：19 45
输出：5 6 18
这个是东北大学秦皇岛分校的oj题1355，不是uva的（这个还得处理输出），附上链接:[http://newoj.acmclub.cn/problems/1355]
这里紫书讲的挺好的：为什么要迭代？
1.分数的个数没有上限
2.理论上，加数的选择也是无限的
3.我们最多找到乐观估价函数
4.这里的回溯法绝对超
但是对于1，2的无限，我们很容易想到，按顺序，取当前分母后面近可能近的分母，这样可以避免重复和减小式子长度。
但是这样容易陷入局部最优产生的全局未优，所以最好深搜+剪枝+及时判断更新

1.dfs的数值处理和变量设定

#include<iostream>
#include<string.h>
#include<algorithm>
#define maxn 20004 
using namespace std;
long long ans[maxn],temp_ans[maxn],temp_len,recommd;//ans:最优答案，temp_ans:深搜暂存的答案，recommd:枚举的深度上限

2.找到小于这个分数的最小单位分数(1/i)

//紫书上的get_first(a,b):满足1/i <= zi/mu 
long long findfir(long long zi,long long mu){long long i=2;while(mu>zi*i)i++;return i;
}

3.约分处理需要

long long gcd(long long a,long long b){ return b?gcd(b,a%b):a; 
}
例：
j=gcd(a,b);
a=a/j;
b=b/j;

4.是否需要更新判断
感觉网上的这个写的都很乱,所以书比较好

mycode:
bool better(long long d){//长度d越小越好，最后的分母越小越好   temp好于ans? if(ans[0]==-1)return true;//如果ans是第一次刚被赋值 for(temp_len=d;temp_len>=0;temp_len--){if(temp_ans[temp_len]!=ans[temp_len])return temp_ans[temp_len]<ans[temp_len]; //temp_ans里有但是ans没有，这个值也一定大于-1 }   return false;
}bookcode:
bool better(long long d){ for(temp_len=d;temp_len>=0;temp_len--){if(temp_ans[temp_len]!=ans[temp_len])return ans[d]==-1||temp_ans[temp_len]<ans[temp_len]; }   return false;
}

5.重点dfs，嘤嘤嘤，找了3个小时bug!!!!

注：基本大框架和回溯法差不多
//当前深度curdeep,分母不能小于trymu,分子zi,分母mu,recommd枚举的最大深度 
bool dfs(long long zi,long long mu,long long trymu,long long curdeep){long long i,j,a,b;//达到条件 if(curdeep==recommd){//到达终点trymu是第curdeep个分数 从0开始 //1.zi!=1if(zi!=1)return false;//2.1 zi==1  分母有没有重复的for(i=0;i<curdeep;i++){if(temp_ans[i]==mu)return false; }//2.2 尝试赋值，进行最优解判断 temp_ans[curdeep]=mu;sort(temp_ans,temp_ans+curdeep);if(better(curdeep))for(i=0;i<=curdeep;i++)ans[i]=temp_ans[i]; return true;}//未达到尝试dfs//trymu必须大于first分母,才不会出现负数，即枚举的起点 trymu=max(trymu,findfir(zi,mu));bool flag=false; for(i=trymu;;i++){//这里退出判断要取等于号，因为剩余个数乘当前分数本来只是个临界值，实际是不能取重复的分母的if(mu*(recommd+1-curdeep)<=zi*i)break; temp_ans[curdeep]=i;//这里只能改动里面定义的变量，zi=zi/j不可以做到改变zi的值并传递给dfs //通分并约分a=zi*i-mu;b=mu*i;j=gcd(a,b);//注意是改变后zi,mu的最大公因数 if(dfs(a/j,b/j,i+1,curdeep+1))flag=true;//后一个数值说这个数值可以用 } return flag;
}

6.主函数（应用dfs)

while(cin>>n>>m){//多组输入，先初始化还原 memset(ans,-1,sizeof(ans));memset(temp_ans,-1,sizeof(temp_ans)); //特判1 if(n==0){cout<<"0\n";continue;}//约分 long long k=gcd(n,m),fir;zi=n/k;mu=m/k;//特判2 if(zi==1)printf("%lld\n",mu);else {long long fir=findfir(zi,mu);//第一个分数 for(recommd=1;;recommd++) {   //因为希望长度越短越好，所以满足就可以尽早breakif(dfs(zi,mu,fir,0))break;}for(k=0;k<=recommd-1;k++)cout<<ans[k]<<" ";cout<<ans[k]<<"\n";}   }