题目

已知由n（n≥2）个正整数构成的集合A={ak|0≤k<n}，将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。

题解

分析

题目要求：两个子集个数相近或相同，和的差值最大

1、两个子集个数

集合的个数

1. 偶数：两个子集元素个数相同
2. 奇数：两个子集元素个数差1，大集合多1个元素

2、元素和的差值

使两个集合的差值最大，对原集合进行从小到大排序，分为大集合小集合，这样差值最大。

3、排序算法

对于第2步，快速排序算法是所有排序算法中最高效的。

快速排序：以升序为例，每一趟选择当前子序列中的一个关键字作为枢轴，将子序列中比枢轴小的移到枢轴前边，比枢轴大的移到枢轴后边。

代码：

void QuickSort(int R[],int low, int high){
int temp = low, i = low, j = high;
while(i<j){
while(i<j&&R[temp]>=R[j]) --j;
if(i<j){
R[i] = R[j];
i++;
}
while(i<j&&R[temp]<=R[i]) ++i;
if(i<j){
R[j] = R[i];
j--;
}
}
R[i] = temp;
//以枢轴将序列分为两部分，分别再次进行快排
QuickSort(R,low,i-1);
QuickSort(R,i+1,high);
}

代码

int main(int R[], int n){
QuickSort(R,0,n);
int i, j = n/2;
for(i=0;i<j;i++){
int S1+=R[i];
}
for(i=j;j<n;j++){
int S2+=R[j];
}
return S2-S1;
}

最后

以上就是可耐冬瓜为你收集整理的2016年408考研算法题题目题解的全部内容，希望文章能够帮你解决2016年408考研算法题题目题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。