如何计算数列和的绝对值最小

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#include <windows.h>



void int_to_big(char* a,int x,int len){

	int i,c;

	c=0;

	memset(a,0,sizeof(char)*len);

	for(i=0;i<len;i++){

		if(x<10){

			a[i]=x;return;

		}

		c=x%10;a[i]=c;x/=10;

	}

}



void print_big(char* a){

	int i,c;

	c=0;

	for(i=31;i>=0;i--){

		if(a[i]!=0){

			if(c==0) c=1;

			printf("%d",a[i]);

		}else{

			if(c!=0) printf("0");

		}

	}

	if(c==0) printf("0");

	printf("\n");

}



void mask_to_msk(int mask,char* msk){

	int i;

	memset(msk,0,sizeof(char)*32);

	for(i=0;i<32;i++){

		if(mask&(1<<i)) msk[i]=1;

	}

}

void msk_to_mask(int* mask,char* msk){

	int i;

	*mask=0;

	for(i=0;i<32;i++) if(msk[i]==1) *mask|=(1<<i);

}



int init_mask(char* a,int* mask,char* msk){

	int i,c;

	char in[32];

	memset(in,0,sizeof(in));

	memset(msk,0,sizeof(char)*32);c=-1;

	for(i=31;i>=0;i--){

		if(a[i]!=0&&c==-1) c=i;

		if(a[i]>1) break;

	}

	if(i==-1) return 1;

	if(c+1==32) return -1;

	msk[c+1]=1;

	msk_to_mask(mask,msk);

	return 0;

}



int is_answer(char* msk,int xx){

	int i,j,lm;

	int cc;

	int b[8],d;

	memset(b,0,sizeof(b));

	for(i=31;i>=0;i--) if(msk[i]!=0) break;

	lm=i+1;

	if(lm%4==0) cc=lm/4;

	else cc=lm/4+1;

	for(i=0;i<cc;i++){

		for(j=0;j<4;j++){

			b[i]=b[i]*10+msk[i*4+3-j];

		}

	}

	d=b[cc-1]%xx;

	for(i=cc-2;i>=0;i--){

		d=d*10000+b[i];

		d=d%xx;

	}

	if(d==0){

		return 1;

	}

	return 0;

}



unsigned prt;

void fun(int x){

	char *pa,*msk;

	int mask,k;

	pa=(char*)malloc(sizeof(char)*32);

	msk=(char*)malloc(sizeof(char)*32);



	//把x转换成10进制表示，并存入pa中

	memset(pa,0,sizeof(char)*32);

	int_to_big(pa,x,32);



	//初始化msk和mask

	k=init_mask(pa,&mask,msk);

	if(k==1){

		printf("%d=>%d\n",x,x);

		free(pa);free(msk);return;

	}else if(k==-1){

		printf("error!\n");

		free(pa);free(msk);return;

	}

	//找答案

	while(1){

		if(is_answer(msk,x)){

			printf("%d=>",x);

			print_big(msk);

			free(pa);free(msk);return;

		}

		mask++;prt=mask;

		if(mask==-1){

			printf("can not find in 32 bits!\n");break;

		}

		mask_to_msk(mask,msk);

	}



	free(pa);free(msk);

}





void mytimer(LPVOID sc){

	unsigned myprt;

	unsigned total=4294967295;

	while(1){

		Sleep(30000);

		myprt=prt;

		printf("test to: %.3f%%\n",100.0*myprt/(1.0*total));

		GetTickCount();

	}

}

int main(){

	HANDLE thrd;

    time_t t1,t2;

    struct tm *pt;



	thrd=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)mytimer,NULL,0,NULL);



	time(&t1);

	pt=localtime(&t1);

	printf("start\t%02d:%02d:%02d\n",pt->tm_hour,pt->tm_min,pt->tm_sec);

	

	fun(10989);

	TerminateThread(thrd,NULL);



	time(&t2);

	pt=localtime(&t1);

	printf("start\t%02d:%02d:%02d\n",pt->tm_hour,pt->tm_min,pt->tm_sec);

	pt=localtime(&t2);

	printf("end\t%02d:%02d:%02d\n",pt->tm_hour,pt->tm_min,pt->tm_sec);

    return 0;

}

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <windows.h>

/***只用替换这里*****************/

#define ASIZE 200 

int a[ASIZE]={-176, 412, 437, -36, 164, -33, -393, 285,

-279, -290, 217, -325, -316, 51, -377, -195,

318, -141, -277, -18, 208, 364, 364, -453,

188, -2, -45, -343, 115, -309, -303, 240,

147, -331, 318, 383, -324, 272, -253, -36,

-419, -173, -392, -213, -55, 119, -50, 1,

-96, 467, 127, 106, -221, -40, 222, 300,

143, -125, -76, 468, -13, -199, 269, -417,

-361, -487, 152, -195, -409, 119, 5, 61,

-114, -484, -438, 384, 229, -321, 106, -213,

480, -174, 113, -29, -330, -24, -312, -376,

212, -55, -287, -386, 458, 300, 103, -155,

262, 312, 80, 56, -314, 428, -132, 357,

-458, 308, -272, -233, -115, -60, -285, -454,

147, -115, 89, -397, 47, 161, -233, -249,

-60, -180, -260, 98, -232, -273, -162, 361,

255, -406, -225, 367, -481, -223, -141, -461,

-264, -106, 289, -358, 40, -231, 430, -432,

286, -253, -8, 438, -142, -80, 495, -176,

155, 267, -51, 332, -67, 275, 142, 374,

143, 39, 442, 374, 428, 398, -471, 201,

-63, 121, -45, 125, -397, -314, -64, 47,

-439, -327, 294, 316, -167, 312, -60, -112,

-35, 211, -180, 131, -245, -207, -284, 33,

-271, 486, -184, 120, -465, 179, 461, -156};

/********************************/



int compar(const void *a,const void *b){

	int *x=(int*)a;

	int *y=(int*)b;

	if(*x>*y) return 1;

	if(*x==*y) return 0;

	return -1;

}



struct level{

	int *now;

	int len;

};



void add(struct level *llv,int n){

	int i=0;

	llv->len=n;

	llv->now=(int*)malloc(sizeof(int)*n);

	memset((char*)(llv->now),0,sizeof(int)*n);

	for(i=0;i<n;i++){

		llv->now[i]=i;

	}

}



void del(struct level *llv){

	free(llv->now);

}



int timeout;

void mytimer(LPVOID sc){

	int seconds;

	seconds=(*(int*)sc)*1000;

	Sleep(seconds);

	timeout=0;

}



void fun(int *array,int size,int n,unsigned int seconds){

	HANDLE thrd;

	int i,j,k;

	int x,y,u,v,o;

	int z,z2;

	int *a;

	int *b;

	int *c;

	char *mask;

	struct level p;

	if(size<=0||size<n||n<=0){

		printf("size<=0||size<n||n<=0 error!\n");return;

	}



	a=(int*)malloc(sizeof(int)*size);

	b=(int*)malloc(sizeof(int)*n);

	c=(int*)malloc(sizeof(int)*size);

	mask=(char*)malloc(sizeof(char)*size);

	memcpy(a,array,sizeof(int)*size);

	memset(b,0,sizeof(int)*n);

	memset(c,0,sizeof(int)*size);

	memset((char*)&p,0,sizeof(struct level));



	qsort(a,size,sizeof(int),compar);

	if(a[0]>=0){

		printf("array error: array need <0 number\n");

		free(mask);free(c);free(b);free(a);return;

	}

	if(a[size-1]<=0){

		printf("array error: array need >0 number\n");

		free(mask);free(c);free(b);free(a);return;

	}



	timeout=1;

	thrd=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)mytimer,(LPVOID)&seconds,0,NULL);



	if(n==1){

		for(i=0;i<size;i++){

			if(i==0){

				z=abs(a[i]);b[0]=a[0];continue;

			}

			z2=abs(a[i]);

			if(z>z2){

				z=z2;b[0]=a[i];

			}

		}

	}

	else if(n==size){

		z2=0;

		for(i=0;i<n;i++){

			b[i]=a[i];z2+=a[i];

		}

		z=abs(z2);

	}

	else if(n<=size/2){

		/**找一个近似解并且优化枚举数组***********************************/

		o=1;

		for(i=0;i<size;i++){

			if(a[i]>=0){

				y=i;break;

			}

		}

		x=y-1;z2=0;

		for(i=0;i<size;i++){

			if(x>=0&&y<size){

				u=a[x]+z2;

				v=a[y]+z2;

				if(abs(u)<abs(v)){

					z2=u;

					if(i==n-1){

						z=abs(z2);b[i]=a[x];

					}

					else if(i<n-1) b[i]=a[x];

					c[i]=a[x];x--;

					continue;

				}else{

					z2=v;

					if(i==n-1){

						z=abs(z2);b[i]=a[y];

					}

					else if(i<n-1) b[i]=a[y];

					c[i]=a[y];y++;

					continue;

				}

			}

			if(x>=0){

				z2=a[x]+z2;

				if(i==n-1){

					b[i]=a[x];z=abs(z2);

				}

				else if(i<n-1) b[i]=a[x];

				c[i]=a[x];x--;

				continue;

			}else{

				z2=a[y]+z2;

				if(i==n-1){

					b[i]=a[y];z=abs(z2);

				}

				else if(i<n-1) b[i]=a[y];

				c[i]=a[y];y++;

				continue;

			}

		}

		/***********************************找一个近似解并且优化枚举数组**/

		if(z>0){

		/**选择****************/

			add(&p,n);

			while(timeout){

				z2=0;

				for(i=0;i<n;i++){

					z2+=c[p.now[i]];

				}

				z2=abs(z2);

				if(z>z2){

					z=z2;

					for(i=0;i<n;i++) b[i]=c[p.now[i]];

					if(z==0) break;

				}

				if(p.now[p.len-1]==size-1){

					for(i=1,j=p.len-2;j>=0;j--,i++){

						if((p.now[j])<(size-1-i)) break;

					}

					if(j<0) break;

					p.now[j]++;

					k=p.now[j]+1;

					for(i=j+1;i<p.len;i++) p.now[i]=k++;

				}else{

					p.now[p.len-1]++;

				}

			}

			/****************选择**/

		}

	}

	else{

		/**找一个近似解并且优化枚举数组***********************************/

		o=1;

		for(i=0;i<size;i++){

			if(a[i]>=0){

				y=i;break;

			}

		}

		x=y-1;z2=0;

		for(i=0;i<size;i++){

			if(x>=0&&y<size){

				u=a[x]+z2;

				v=a[y]+z2;

				if(abs(u)<abs(v)){

					z2=u;

					if(i==n-1){

						z=abs(z2);b[i]=a[x];

					}

					else if(i<n-1) b[i]=a[x];

					c[i]=a[x];x--;

					continue;

				}else{

					z2=v;

					if(i==n-1){

						z=abs(z2);b[i]=a[y];

					}

					else if(i<n-1) b[i]=a[y];

					c[i]=a[y];y++;

					continue;

				}

			}

			if(x>=0){

				z2=a[x]+z2;

				if(i==n-1){

					b[i]=a[x];z=abs(z2);

				}

				else if(i<n-1) b[i]=a[x];

				c[i]=a[x];x--;

				continue;

			}else{

				z2=a[y]+z2;

				if(i==n-1){

					b[i]=a[y];z=abs(z2);

				}

				else if(i<n-1) b[i]=a[y];

				c[i]=a[y];y++;

				continue;

			}

		}

		memset(a,0,sizeof(int)*size);

		for(i=0;i<size;i++) a[i]=c[size-i-1];

		/***********************************找一个近似解并且优化枚举数组**/

		if(z>0){

		/**排除****************/

			add(&p,size-n);

			while(timeout){

				memset(mask,0,sizeof(char)*size);

				for(i=0;i<size-n;i++) mask[p.now[i]]=1;

				z2=0;

				for(i=0;i<size;i++) if(mask[i]==0) z2+=a[i];

				z2=abs(z2);

				if(z>z2){

					z=z2;j=0;

					for(i=0;i<size;i++) if(mask[i]==0) b[j++]=a[i];

					if(z==0) break;

				}

				if(p.now[p.len-1]==size-1){

					for(i=1,j=p.len-2;j>=0;j--,i++){

						if((p.now[j])<(size-1-i)) break;

					}

					if(j<0) break;

					p.now[j]++;

					k=p.now[j]+1;

					for(i=j+1;i<p.len;i++) p.now[i]=k++;

				}else{

					p.now[p.len-1]++;

				}

			}

			/**排除****************/

		}

	}



	printf("n=%d:\n",n);

	if(timeout) printf("[");

	else printf("time out! the best test answer find in %d seconds is:\n[",seconds);

	for(i=0;i<n-1;i++){

		printf("%d, ",b[i]);

	}

	printf("%d], |SUM|=%d\n",b[i],z);

	TerminateThread(thrd,NULL);

	del(&p);free(mask);free(c);free(b);free(a);

}



void main(){

	int i;

	for(i=1;i<=ASIZE;i++) fun(a,ASIZE,i,10);

}