poj 1011 搜索（剪枝）

#include<cstdio> #include<cstring> #include<algorithm> #define MIN(x,y) ((x)>(y)?(y):(x)) using namespace std; int d[70],m[70],total,flag,vis[70],n,t; int dfs(int begin,int aim,int rest) { if(rest==0&&aim==0) return 1; if(aim==0) { if(dfs(0,t,rest)) return 1; else return 0; } for(int i=begin;i<n;i++) { if(vis[i]) continue; if(d[i]>aim) continue; vis[i]=1; if(dfs(i+1,aim-d[i],rest-1)) return 1; vis[i]=0; if(aim==t||aim==d[i]) break; } return 0; } bool cmp(int a,int b) { return a>b; } int main() { while(~scanf("%d",&n)&&n) { int x,sum; memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); total=0x3f3f3f3f; sum=0; for(int i=0;i<n;i++) { scanf("%d",&d[i]); sum+=d[i]; total=MIN(total,d[i]); } sort(d,d+n,cmp); for(t=total;t<=sum;t++) { if(sum%t) continue; memset(vis,0,sizeof(vis)); if(dfs(0,t,n)) { printf("%d\n",t); break; } } } }