zju 2868 求剪枝方法解决方法

zju 2868 求剪枝方法
http://acm.zju.edu.cn/show_problem.php?pid=2868

用的是0_1 搜索（就是选与不选）， 加上一点剪枝，只是剪得不好，结果超时了，想知道怎么剪更好。

#include "stdio.h"
#include "stdlib.h"

int teamA,teamB;
int min;
int sum;
int arry[50];

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


void Select(int step,int n)
{
if(step>n)
{
if( abs(teamA-teamB) < min )
min=abs(teamA-teamB);
return;
}

if(2*teamA-sum > min)
return;
if(2*teamB-sum>min)
return ;

teamA+=arry[step];
Select(step+1,n);
teamA-=arry[step];

teamB+=arry[step];
Select(step+1,n);
teamB-=arry[step];
}

int main()
{
int cas,n;
int i;

scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
min=0;sum=0;

for(i=0;i<n;i++)
{
scanf("%d",&arry[i]);
sum+=arry[i];

}

qsort(arry,n,sizeof(int),cmp);

teamA=teamB=0;
for(i=0;i<n;i++)
{
if(teamA>=teamB)
teamB+=arry[i];
else
teamA+=arry[i];
}
min=abs(teamA-teamB);

teamA=arry[0];teamB=0;
Select(1,n);
printf("%d\n",min);
}
return 0;
}

[解决办法]
2665800 2007-11-02 12:09:44 Accepted 2868 C 00:00.87 1560K tailzhou 

#include <stdio.h>
#include <stdlib.h> 

#define MAX_LEN 34

int num[MAX_LEN];

int diff1[0x1<<17];
int diff2[0x1<<17];


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

int main()
{
int t;

scanf("%d", &t);
while (t--)
{
int n;
int i,j,k;
int sum1=0,sum2=0,min_diff;
scanf("%d", &n);
i=0;
while (i<n)
{
scanf("%d", num+i);
if (i<n/2) sum1+=num[i];
else sum2+=num[i];
i++;
}

for (i=0;i<(0x1<<(n/2)) ; i++)
{
int tmp=0;
j=i;
k=0;
while (j>0)
{
if (j & 0x1) tmp+=num[k];
k++;
j>>=1;
}
diff1[i]=abs(sum1-2*tmp);
}

for (i=0;i<(0x1<<(n-n/2)) ; i++)
{
int tmp=0;
j=i;
k=0;
while (j>0)
{
if (j & 0x1) tmp+=num[k+n/2];
k++;
j>>=1;
}
diff2[i]=abs(sum2-2*tmp);
}

qsort(diff1,0x1<<(n/2),sizeof(int),cmp); 
qsort(diff2,0x1<<(n-n/2),sizeof(int),cmp);

min_diff=abs(diff1[0]-diff2[0] );
i=j=0;
while (i<0x1<<(n/2) && j<0x1<<(n-n/2))
{
while (j<0x1<<(n-n/2) && diff2[j]>diff1[i]) j++;
if (j>0 && abs(diff2[j-1]-diff1[i])<min_diff) min_diff=abs(diff2[j-1]-diff1[i]);
if (j<0x1<<(n-n/2) && abs(diff2[j]-diff1[i])<min_diff) min_diff=abs(diff2[j]-diff1[i]);
if (min_diff==0) 
{
break;
}
i++;
}
printf("%d\n",min_diff);
}

return 0;
}