22/5/24

1，dfs迭代加深：eg1：加成序列；2，双向dfs：eg1：送礼物；

1，dfs迭代加深；

迭代加深一般适用于明确了最终的答案所处的位置（一般是浅层），而暴搜会搜很多无用的深层，导致浪费许多计算，所以就要明确搜索方向；迭代加深，顾名思义就是一层一层加深；

eg1：加成序列；

数据范围n<=100;

这就是这道题的精髓；

因为1 2 4 8 16 32 64 128 ，所以很容易得出最终的序列长度不会很长，不会超过10；

答案位于浅层，所以就迭代加深去做；

然后就是一些剪枝优化：

优先枚举大的数；

排除等效冗余；

#pragma GCC optimize(2)
#include
#define rep1(i,a,n) for( int i=a;ia;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i) memset((a),(i),sizeof (a))
#define memcpy(a,i) memcpy((a),(i),sizeof (a))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "n"
#define lowbit(m) (-m&m)
#define YES cout<<"YESn"
#define NO cout<<"NOn"
#define Yes cout<<"Yesn"
#define No cout<<"Non"
#define yes cout<<"yesn"
#define no cout<<"non"
#define yi first
#define er second
using namespace std;
typedef pair PII;
typedef pairPLL;
typedef pair PIII;
typedef long long ll;
typedef double dob;
const int N=110;
int n,path[N];
bool st[N];
bool dfs(int u,int k)
{
    if(u==k)return path[u-1]==n;
    memset(st,0);
    per2(i,u-1,0)
    {
        per2(j,i,0)
        {
            int s=path[i]+path[j];
            if(s>n||s<=path[u-1]||st[s])continue;
            st[s]=1;
            path[u]=s;
            if(dfs(u+1,k))return 1;
        }
    }
    return 0;
}
signed main()
{
    quick_cin();   
    path[0]=1;
    while (cin>>n,n)
    {
        int k=1;
        while(!dfs(1,k))k++;
        rep1(i,0,k)cout< 
2，双向dfs；
 
类似于双向bfs，节省搜索后期大量的空间和时间；
 
 
eg1：送礼物；
 
 
 
直接暴搜，2^46次方，会炸时间和空间；
 
所以考虑双向搜索（图片来自acwing Bug—Free）；
 
 
 
 k=n/2；如果k=n/2+2，n=1时会陷入死循环；
 
#pragma GCC optimize(2)
#include
#define rep1(i,a,n) for( int i=a;ia;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i) memset((a),(i),sizeof (a))
#define memcpy(a,i) memcpy((a),(i),sizeof (a))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "n"
#define lowbit(m) (-m&m)
#define YES cout<<"YESn"
#define NO cout<<"NOn"
#define Yes cout<<"Yesn"
#define No cout<<"Non"
#define yes cout<<"yesn"
#define no cout<<"non"
#define yi first
#define er second
using namespace std;
typedef pair PII;
typedef pairPLL;
typedef pair PIII;
typedef long long ll;
typedef double dob;
const int N=1<<25;
int n,m,k;
int g[50],weigths[N],cnt,ans;
void dfs(int u,int s)
{
    if(u==k)
    {
        weigths[cnt++]=s;
        return;
    }
    if((ll)s+g[u]<=m)dfs(u+1,s+g[u]);
    dfs(u+1,s);
}
void dfs2(int u,int s)
{
    if(u==n)
    {
        int l=0,r=cnt-1;
        while (l>1;
            if(weigths[mid]+(ll)s<=m)l=mid;
            else r=mid-1;
        }
        if(weigths[l]+(ll)s<=m)ans=max(ans,weigths[l]+s);
        return;
    }
    if((ll)s+g[u])dfs2(u+1,s+g[u]);
    dfs2(u+1,s);
}

signed main()
{
    quick_cin();   
    cin>>m>>n;
    rep1(i,0,n)cin>>g[i];
    sort(g,g+n,greater());
    k=n>>1;
    dfs(0,0);
    sort(weigths,weigths+cnt);
    int t=1;
    rep1(i,1,cnt)
    {
        if(weigths[i]!=weigths[i-1])
        {
            weigths[t++]=weigths[i];
        }
    }
    cnt=t;
    dfs2(k,0);
    cout<