数组分割

题目：将一个没有排序，元素个数为2n的正整数数组，分割为元素个数为n的两个数组，使两个子数组的和最接近。

问题转换：从一个数组中找到和最接近给定值的一组元素。

思路：

o(2n)算法：

举例1：S中前n个元素中任意i(0,1…n)个元素的可能和的集合

s={1,4,5}：

F0 = {0}; //没有元素

F1 = {0,1}; //s中前1个元素，可能的和集合

F2 = {0,1,4,5}//s中前2个元素，可能的和集合

F3 = {0,1,4,5,6,9,10} //s中前3个元素，可能的和集合

举例2：S中前n个元素中i（特定）个元素的可能和的集合

对于第一个元素：1

Heap[0] = {0}

Heap[1] = {1}

对于第二个元素：4

Heap[2] = {5}

Heap[1] = {4}

对于第三个元素：5

Heap[3] = {10}

Heap[2] = {6,9}

Heap[1] = {5}

综合上述：Heap[0]={0}, //s中0个元素的和集合

Heap[1]={1,4,5}, //s中1个元素的和的集合

Heap[2]={5,6,9}, //s中2个元素的和的集合

Heap[3]={10} //s中3个元素的和的集合

本题：求2*n个元素中n个元素的所有可能的和的集合：Heap[n]

伪码实现：

for(k=1; k<=2*n; k++){

i_max = min(k-1,n-1);

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

for each v in Heap[i]

insert(v+arr[k],Heap[i+1])

}

}

改进算法：

Heap[i]保存i个数所有可能和集合=>isOk[i][v]=true/false（是否有i个数的和为v）

for(k=1; k<=2*n; k++){

i_max = min(k-1,n-1);

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

for(v=1; v<=sum/2; v++){

if(v >= arr[k] && isOk[i-1][v-arr[k]])

isOk[i][v] = true;

}

}

}

时间复杂度为：o(n*n*sum)

当sum不大，可以采用此方法。