搜索剪枝

· · 个人记录

剪枝是提高搜索算法时空效率，使得算法在优越性上大大优化的技巧。有的时候暴力搜索（也叫爆搜）过不了时限的算法，通过各种剪枝+优化之后就能成功AC。可见剪枝的重要性。无论是正解搜索算法还是想不到正解无奈之下选择的骗分算法，剪枝都是一类不得不学、不得不会的知识点。

  1. 可行性剪枝

当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回。

即：走不了，就回去。

  1. 排除等效冗杂

所谓排除等效冗余，就是当几个枝桠具有完全相同的效果的时候，只选择其中一个走就可以了。

即：都可以，选一个。

  1. 最优性剪枝

所谓最优性剪枝，是在我们用搜索方法解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候，已经比已经搜到的最优解要不优了，那么这个方案肯定是不行的，即刻停止搜索，进行回溯。

即：有比较，选最优。

  1. 顺序剪枝

普遍来讲，搜索的顺序是不固定的，对一个问题来讲，算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。

即：有顺序，按题意。

  1. 记忆化

记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理：

就是记录搜索的每一个状态，当重复搜索到相同的状态的时候直接返回。

即：搜重了，直接跳。

P1120小木棍

以下大篇幅引用了Kaori dalao的题解：

1.大致方向分析

n <= 65,a[i] <= 50 -> ans <= 3250;

1.我们可以很容易的发现,max(ans)=a[1]+a[2]+...+a[n];而min(ans)=max(a[i]);且ans的值域很小，于是我们考虑直接枚举。然后，我们再思考一下：可发现ans 如果 > sum/2;则所有的小木棍只能拼成一根，即ans 只可能<= sum/2;所以我们只需要进行max(a[i]) to sum/2 的枚举

2.我们可以考虑到当ans % sum != 0的话，这些木棍是拼不出整数根的,所以直接continue掉

这里我们运用了1.可行性剪枝。

2.预处理分析

1.一根长木棍肯定比几根短木棍拼成同样长度的用处小，即短的木棍可以更灵活组合，所以对输入的所有木棍按长度从大到小排序，从长到短地将木棍拼入(短木棍可能可以拼出长木棍）。

2.我们可以发现啊，同一个长度的木棍可以有多个，而当dfs返回拼接失败，需要更换当前使用的木棍时，不要再用与当前木棍的长度相同的木棍，因为当前木棍用了不行，改成与它相同长度的木棍一样不行。所以可以预处理出排序后每根木棍后面的最后一根与这根木棍长度相等的木棍（程序中的next数组），它的下一根木棍就是第一根长度不相等的木棍了。

3.显而易见的是我们需要运用vis[]来记录哪根木棍是否被用过

这里我们运用了1.顺序剪枝 2.排除等效冗余 3.记忆化

3.ok啊，开始我们愉快的搜索了 1.根据大方向分析里的分析，我们可以直接使用for循环来探查每一个长度是否符合要求，当第一次发现符合要求时便直接输出答案即可

2.在搜索中的每一层直接判断rest是否等于0且所有木棍都被恰好使用(已拼数量 = a[1]+a[2]+...+a[n] / ans），如是，则一路跳出递归

3.在搜索下一个要使用的木棍时，二分找第一个 木棍长度不大于未拼长度rest 的位置

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    if(f) return x;
    return 0-x;
}
int n,m,a[66],next[66],cnt,sum,len;
bool used[66],ok; //used数组即为vis数组，记录每根木棍是否用过；ok记录是否已找到答案。 
bool cmp(int a,int b){return a>b;}
void dfs(int k,int last,int rest){ //k为正在拼的木棍的编号，last为正在拼的木棍的前一节编号，rest为该木棍还未拼的长度
    int i;
    if(!rest){ //未拼的长度为0，说明这根原始长棍拼完了，准备拼下一个 
        if(k==m){ok=1; return;} //全部拼完并符合要求，找到答案，直接返回 

        for(i=1;i<=cnt;i++) //找一个还没用的最长的木棍打头即可。反正要想全都拼接成功，每根木棍都得用上 
            if(!used[i]) break;
        used[i]=1; 
        dfs(k+1,i,len-a[i]);
        used[i]=0;
        if(ok) return; //找到答案就退出 
    }
    //二分找第一个 木棍长度不大于未拼长度rest 的位置 
    int l=last+1, r=cnt, mid;
    while(l<r){
        mid=(l+r)>>1;
        if(a[mid]<=rest) r=mid;
        else l=mid+1;
    }
    for(i=l;i<=cnt;i++){
        if(!used[i]){ //判断木棍是否用过 
            used[i]=1;
            dfs(k,i,rest-a[i]);
            used[i]=0;
            if(ok) return; //找到答案就退出 

            if(rest==a[i] || rest==len) return; //优化7 
            i=next[i]; 
            if(i==cnt) return;
        }
    }
    //到了这里，说明这时候拼不成当前这根原始木棍了，传回失败信息并修改之前拼的木棍 
}
int main(){
    n=read();
    int d;
    for(int i=1;i<=n;i++){
        d=read();
        if(d>50) continue;
        a[++cnt]=d;
        sum+=d;
    }
    sort(a+1,a+cnt+1,cmp); //木棍按长度从大到小排序 
    //预处理next数组 
    next[cnt]=cnt;
    for(int i=cnt-1;i>0;i--){
        if(a[i]==a[i+1]) next[i]=next[i+1];
        else next[i]=i;
    }
    for(len=a[1];len<=sum/2;len++){ //枚举原始长度 
        if(sum%len!=0) continue; //如果不能拼出整数根 就跳过 
        m=sum/len; 
        ok=0;
        used[1]=1;
        dfs(1,1,len-a[1]);
        used[1]=0;
        if(ok){printf("%d\n",len); return 0;} //输出答案，退 
    }
    printf("%d\n",sum); return 0;
}