> #include<iostream>
> using namespace std;
> /*最优化剪枝：如果当前搜到的s+f的值加上后面最多能达到的s+f的值小于已经搜得的最大值，就退出；
> 可行性剪枝：如果当前搜到的s(或f)值＜0，那么如果s(或f)加上后面最多能得到的s(或f)值＜0，就退出。*/
> struct point
> {
> 	int x,y;
> };
> int max;
> int ms,mx,my;
> point p[101];
> int mins[101],minx[101],miny[101];
> int j;
> 
> int cmp(const void *a, const void *b)
> {
> 	return((*(point *)b).x+(*(point *)b).y)-((*(point *)a).x+(*(point *)a).y);
> }
> 
> void dfs(int i,int s,int x,int y)//i表示搜到第几点。
> {
> 	if(s>max&&x>=0&&y>=0)
> 		max=s;
> 	if(i==j)
> 		return ;
> 	if(s+mins[i]<max)//剪枝
> 		return ;
> 	if(x<0&&x+minx[i]<0)//剪枝
> 		return ;
> 	if(y<0&&y+miny[i]<0)//剪枝
> 		return ;
> 
> 	dfs(i+1,s,x,y);
> 	dfs(i+1,s+p[i].x+p[i].y,x+p[i].x,y+p[i].y);
> }
> 	
> main()
> {
> 
> 	int i,k,n,a,b;
>     cin>>n;
> 	j=0;
> 	max=0;
> 	ms=0;mx=0;
> 	my=0;
> 	for(i=0;i<n;i++)
> 	{
> 		cin>>a>>b;
> 		if(a>=0&&b>=0&&a+b>0)
> 		{
> 			mx+=a;
> 			my+=b;
> 			ms=ms+a+b;
> 		}
> 		else if(a+b>0)
> 		{
> 			p[j].x=a;
> 			p[j].y=b;
> 			j++;
> 		}
> 	}
>     qsort(p, j, sizeof(point), cmp);
>     mins[j-1]=p[j-1].x+p[j-1].y;//求后面最多能达到的s+f的值，和后面最多能得到的s(或f)值
> 	if(p[j-1].x>0)
> 		minx[j-1]=p[j-1].x;
> 	else
> 		minx[j-1]=0;
> 	if(p[j-1].y>0)
>     	miny[j-1]=p[j-1].y;
> 	else
> 		miny[j-1]=0;
> 	for(k=j-2;k>=0;k--)
> 	{
> 		if(p[k].x>0)
> 			minx[k]=p[k].x+minx[k+1];
> 		else
> 			minx[k]=minx[k+1];
> 		if(p[k].y>0)
> 			miny[k]=p[k].y+miny[k+1];
> 		else
> 			miny[k]=miny[k+1];
> 		mins[k]=p[k].x+p[k].y+mins[k+1];
> 	}
> 	dfs(0,ms,mx,my);
> 	cout<<max<<endl;
> 	return 0;
> }
> 

• 改了一下，超时了，不知怎样剪枝了。高手麻烦看一下。。。 (1603) luckystar 2007-08-27 13:15:19