2016 年

将一个数组分为两个不相交的子集，元素个数分别为 $n_1$ 、 $n_2$ ，元素之和分别为 $S_1$ 、 $S_2$ 。要使 $n_1-n_2$ 最小且 $S_1-S_2$ 最大。

int partion(int A[],int low,int high){
	int pivot=A[low];
	while(low<high){
		while(low < high && pivot<=A[high]){
			high--;
		}
		A[low]=A[high];
		while(low < high && pivot >=A[low]){
			low++;
		}
		A[high]=A[low];
	}
	A[low]=pivot;
	return low;
}
 
void q_sort(int A[],int low,int high){
	while(low<high){
		int pivot=partion(A,low,high);
		q_sort(A,low,pivot-1);
		q_sort(A,pivot+1,high);
	}
}
 
int get_sum(int A[],start,end){
	int sum=0;
	for(int i=start;i<=end;i++){
		sum+=A[i];
	}
	return sum;
}
 
int setPartion(int A[],int n){
	q_sort(A);
	int s1,s2;
	s1=get_sum(A,0,n/2-1);
	s2=get_sum(A,n/2,n-1);
	return s2-s1;
}