1011.c

北大在线测试系统1011题 搜索加剪枝

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define max 64

int sl[max],vis[max],n;
int sum,lg;

int cmp(const void * a, const void * b)
{
      return (*(int *)b) - (*(int *)a);
}

int DFS(int times,int le,int pos)
{
    int i;
    for(i=pos;i<n;i++){
       if(!vis[i]&&le>=sl[i]){
            vis[i]=1;
            if(times==1&&le-sl[i]==0){
                return 1;}
             if(le-sl[i]==0){
                 if(DFS(times-1,lg,0)==1) return 1;
                 else{vis[i]=0;return 0;}
                    }
            else {
                    if(DFS(times,le-sl[i],i+1)==1) return 1;
                    else if(lg==le) {vis[i]=0;return 0;}
                }
            vis[i]=0;
        }
    }
return 0;
}

int main()
{
      int i;
      while(scanf("%d",&n),n>0){
          memset(sl, 0, sizeof(sl));   sum=0;
          for(i=0;i<n;i++){
              scanf("%d",&sl[i]);
              sum+=sl[i];
          }
          qsort(sl, max, sizeof(int),cmp);
          for(i=sl[0];i<=sum;i++){
              if(sum%i==0){
                  memset(vis, 0, sizeof(vis));
                  if(i==sum){ printf("%d\n",sum); break;}
                  lg=i;
                  if(DFS(sum/i,i,0)){ printf("%d\n",i); break;}
              }
          }
      }
      return 0;
}