题目大意：有一堆木棍 由几个相同长的木棍截出来的，求那几个相同长的木棍最短能有多短？

深搜+剪枝 具体看代码

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <string>

#define oo 0x13131313

using namespace std;

int N,M;

int A[100],Max=-1,Sum,NN;

int visit[100];

bool cmp(int a,int b)

{

    return a>b;

}

void input()

{

    memset(visit,0,sizeof(visit));

    Max=-1;Sum=0;

    for(int i=1;i<=N;i++)

    {

        scanf("%d",&A[i]);

        if(A[i]>Max) Max=A[i];

        Sum+=A[i];

    }

}

int dfs(int now,int nown,int pos)

{

    int ok=0;

    if(nown==NN) return 1;

        for(int i=pos+1;i<=N;i++)

        {

            if(visit[i]==0)

            {

                if(now+A[i]<=M)

               {

                visit[i]=1;

                if(now+A[i]==M) ok=dfs(0,nown+1,0);

                else  ok=dfs(now+A[i],nown,i); //剪枝1  次要剪枝

                visit[i]=0;

                if(ok) return 1;

                if(now==0) return 0;        //剪枝2  必须剪枝 now==0 表示这是一个新的一根但i却依旧不能加进去

                                            //       在新的一根中都不能满足，说明未来所有的木棍中都没有他的容身之所，直接return 0；本题精华所在

                while(A[i]==A[i+1]) i++;    //剪枝3  次要剪枝 如果这个不满足的话，与他相同的也不可能满足这根

               }

            }

        }

    return 0;

}

void solve()

{

    sort(A+1,A+N+1,cmp);

    for(int i=Max;i<=Sum;i++)

    {

       if(Sum%i==0)

       {

           memset(visit,0,sizeof(visit));

           M=i;

           NN=Sum/i;

           if(dfs(0,0,0)) {

                            printf("%d\n",M);

                            break;

                        }

       }

    }

}

void init()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

}

int main()

{

   // init();

	while(cin>>N&&N!=0)

    {

        input();

        solve();

    }

}