小木棍 （剪枝）

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入格式
第一行为一个单独的整数 表示砍过以后的小木棍的总数。 第二行为 个用空格隔开的正整数，表示 根小木棍的长度。

输出格式
输出仅一行，表示要求的原始木棍的最小可能长度。
样例输入

9
5 2 1 5 2 1 5 2 1

样例输出

6

剪枝
从最优方面
1.设所有木棍的长度和为sum,那么原长度一定能被sum整除
2.木棍原来的长度一定大于等于所有木棍中最长的一根
从可行性方面
3.短木棍更灵活组合，可以对输入的木棍进行从大到小排序
4.当木棍i拼合原始木棍时，可以从i+1的木棍开始搜
5.如果当前最长的木棍拼不出原木棍长度，那就换一个原始木棍长度
6.相同长度的木棍不要搜索多次
7.搜到的几根木棍如果大于原木棍，直接返回
8.当前剩下的木棍如果拼凑不出原长度，直接返回
9.找到结果，在能返回的地方返回上一层

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int len,n,used[1050],sum=0,m,bj,maxx=0;
int a[1050];
const int inf=0x3f3f3f3f;
bool cmp(int x,int y)
{
    return x>y;
}
void read()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        maxx=max(maxx,a[i]);
        sum+=a[i];
    }
    sort(a+1,a+n+1,cmp);   //从大到小排
}
void dfs(int k,int last,int rest)     //第k根木棒   last为k的前一根木棒 还需拼接的长度
{
    int i,j;
    if(k==m)   //当前木棍数量==所需拼接数量 拼接成功
    {
        bj=1;
        return ;
    }
    if(rest==0)          //当前这一根木棍拼接好了  继续递归拼接下一根
    {
        for(i=1; i<=n; i++)
            if(!used[i])
            {
                used[i]=1;
                break;
            }
        dfs( k+1,i,len-a[i]);   //原始木棍减去拼接木棍==还需要的长度
        //i只是可以拼接是否满足还要下一步检验
    }
    for( i=last+1; i<=n; i++)
    {
        if(!used[i]&&(rest-a[i])>=0)
        {
            used[i]=1;
            dfs(k,i,rest-a[i]);
            used[i]=0;     //回溯  如果上面i拼接不符 回到这里要取消标记
            j=i;
            while(i<n&&a[i]==a[j])   //不要用for循环  i没办法赋值
            {
                i++;       //跳过，直到不相等
            }
            if(i==n)     //找到最后了
                return ;   //结束深搜
        }
    }
}
void solve()
{
    for(int i=maxx; i<=sum; i++)
    {
        if(sum%i==0)
        {
            memset(used,0,sizeof(used));
            len=i;        //记录原始木棍长度
            used[1]=1;   //标记第一个木棍

            bj=0;
            m=sum/i;      //保存所需木根数
            dfs(1,1,len-a[1]);
            if(bj)
            {
                printf("%d\n",len);
                break;
            }

        }
    }
}
int main()
{
    read();
    solve();
    return 0;
}