#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[105],ans,sum,flag,v[105],f[105],num,minh;
int cmp(int x,int y){
return x>y;
}
void dfs(int x,int p){
if(p==x){
//cout<<x<<" “;
for(int i=1;i<=n;i++){
if(v[i]) {
f[i]=1;
// cout<<a[i]<<” ";
}
flag=1;
}
//cout<<endl;
num++;
return;
}
if(flag) return;
for(int i=1;i<=n;i++){
if(v[i]||a[i]+p>x||f[i]) continue;
v[i]=1;
dfs(x,p+a[i]);
v[i]=0;
if(flag) return;
}
return;
}
int main(){
minh=1e5;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
sum+=a[i];
minh=min(minh,a[i]);
}
sort(a+1,a+n+1,cmp);
//cout<<sum<<endl;
for(ans=minh;ans<=sum;ans++){
if(sum%ans!=0) continue;
memset(f,0,sizeof f);
num=0;
for(int i=1;i<=sum/ans;i++){
flag=0;
dfs(ans,0);
}
if(num>=sum/ans) break;
}
cout<<ans;
return 0;
}
是小木棍吧。。。
1、minh的赋值要改为minh=max（minh，a[i]）
因为答案不可能小于裁剪后的长度
2、利用flag退出dfs太耗时间了，可直接在dfs里验证答案正确性后用exit(0)退出程序