题目大意：用n根长度未必相等的木棒匹配出最多数量的等长木棒。
题目分析：枚举所有可能的等长木棒的长度，通过DFS的方式逐根匹配，在此过程中要剪枝。先将木棒长度按从大到小排序，也就是说匹配每一根等长木棒时总是优先挑选长的。剪枝方案如下：1. 若第i-1根木棒在当前方案的匹配中没有用到并且length[i]==length[i-1]，则第i根木棒也不可能用到；2.若已匹配成功cnt根等长木棒，而第cnt+1根匹配不成功，则要剪枝；3.若在匹配第cnt+1根木棒时，最长的那根木棒stick会第一个被选择，若此时第cnt+1根等长木棒匹配失败，则第cnt+1根等长木棒无须继续匹配，返回第cnt根等长木棒的匹配即可，因为与stick在此次匹配时匹配的可选木棒范围要比以后更大，此次都匹配不成，以后更匹配不成，要重新匹配第cnt根木棒，得以产生新的最长木棒stick’，再由此尝试匹配第cnt+1根等长木棒。
以上三条缺一不可！！！
代码如下：
# include<iostream>
# include<cstdio>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std; int w[100],n,vis[100]; bool myComp(const int &a,const int &b)
{
return a>b;
} bool dfs(int cur,int g,int id,int cnt,int sum)
{
if(g*cnt==sum)
return true; for(int i=id;i<n;++i){
if(vis[i])
continue;
if(i&&!vis[i-1]&&w[i-1]==w[i])///剪枝1
continue;
if(cur+w[i]==g){
vis[i]=1;
if(dfs(0,g,0,cnt+1,sum))
return true;
vis[i]=0;
return false;///剪枝2
}
else if(cur+w[i]<g){
vis[i]=1;
if(dfs(cur+w[i],g,i+1,cnt,sum))
return true;
vis[i]=0;
if(cur==0)
return false;///剪枝3
}
}
return false;
} int main()
{
int sum;
while(~scanf("%d",&n)&&n)
{
sum=0;
for(int i=0;i<n;++i){
scanf("%d",w+i);
sum+=w[i];
} sort(w,w+n,myComp); int flag=0;
for(int g=w[0];g<=sum/2;++g){
if(sum%g==0){
memset(vis,0,sizeof(vis));
if(dfs(0,g,0,1,sum)){
flag=1;
printf("%d\n",g);
break;
}
}
}
if(!flag)
printf("%d\n",sum);
}
return 0;
}