文章目录
迭代加深
深搜需要不断深入，但如果答案在某个较浅的节点上。如果一开始就选错了分支，这样会浪费大量时间。
当搜索树规模随着层次的深入增长很快，并且我们能确定答案在一个较浅的节点时，
就可以采用迭代加深。
加成序列
思路
根据题意分析，m的值不会很大，而不断深搜枚举两个数的和，结果有很多。可以用迭代加深，从1开始限制深搜长度，若搜索失败，
就增加深度限制重新搜索，直到找到答案。
先以序列的长度为k=1,再不断k++.每次进行dfs,直到满足条件打印。
定义dfs,调用u,k。分别表示当前序列长度，搜索的长度范围。
两重循环,用已确定的数字，遍历 i,j相加的结果，满足条件，接着dfs向后加。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=110;
int n,path[N];
bool dfs(int u,int k)//u表示当前层数
{
if(u==k) return path[u-1]==n;//达到k层了，判断尾项是不是n
bool st[N]={0};//标记 去重
for(int i=u-1;i>=0;i--)
for(int j=i;j>=0;j--)
{
int s=path[i]+path[j];//i可以=j,遍历各种相加结果
if(s>n||s<=path[u-1]||st[s])//s必须大于前面的值
continue;
st[s]=true;
path[u]=s;//确定第path[u],接着往后加
if(dfs(u+1,k))
return true;
}
return false;
}
signed main()
{
IOS
path[0]=1;
while(cin>>n&&n){
int k=1;
while(!dfs(1,k))
k++;//k表示层数，不断递增，扩大范围
for(int i=0;i<k;i++)
cout<<path[i]<<" ";
cout<<'\n';
}
return 0;
}
双向搜索
除了迭代加深，双向搜索也可以避免在深层子树上浪费时间。有些题目不但有初态，还有终态。可以采用双向搜索——从初态和终态出发各搜索一半状态，产生两颗深度减半的搜索树，在中间交会，组合成最终答案
送礼物
n个数字，任选几个相加，使和不超过M,最大和是多少
思路
对于每一个，可选可不选，复杂度是O(2 ^N),太高。这时候就可以用双向搜索，分两半。
先排序优化搜索，将前一半搜完记录在weights数组中，将该数组排序,去重，当后一半每选完一次，就对weights二分查找合适的最大数
搜索是从前往后，选择当前数，一条dfs路，不选另一条路，不用考虑太多。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=1 << 25;//k最大时25，有2^25种方案
int n,m,k;
int g[50]; //存储所有物品的重量
int weights[N];//存储能凑出来的所有重量
int cnt=0;
int ans;
//u表示枚举到那个数了，s表示当前和
void dfs1(int u,int s){
if(u==k){
weights[cnt++]=s;//前一半枚举完，记录一下
return;
}
dfs1(u+1,s);//不选该物品
if(s+g[u]<=m)
dfs1(u+1,s+g[u]);//选择该物品
}
void dfs2(int u,int s)
{
if(u==n){//如果找完n个节点，二分一下
int l=0,r=cnt-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(weights[mid]<=m-s)
l=mid;
else
r=mid-1;
}
ans=max(ans,weights[l]+s);
return;
}
dfs2(u+1,s);//不选择当前
if(s+g[u]<=m)
dfs2(u+1,s+g[u]);
}
signed main(){
IOS
cin>>m>>n;
for(int i=0;i<n;i++)
cin>>g[i];
sort(g,g+n,greater<int>());
k=n>>1;
dfs1(0,0);//对前k个进行搜索，可能结果记录在weights中
sort(weights,weights+cnt);//再排序，为二分做准备
//去重
int t=1;
for(int i=1;i<cnt;i++)
if(weights[i]!=weights[i-1])
weights[t++]=weights[i];
cnt=t;
dfs2(k,0);
cout<<ans<<'\n';
return 0;
}