数组划分问题

问题描述：给定一个正整数数组a，大小为n，数组的每个元素取值于[0,1,...,K],K>0，将这个数组划分为两个集合A1和A2，使得这两部分元素和最小，S1为A1所有元素求和，S2为A2所有元素求和，即|S1-S2|最小。

分析：由于数组中的元素都是正数，我们用SUM来表示数组a的所有元素的和，那么我们只要求一个集合，使得这个集合所有元素的和尽量接近SUM/2即可，我们用Q[i,j]表示用数组中任意的i个元素求和，和是否为j，如果是，那么Q[i,j]=1,否则Q[i,j]=0. 那么状态转移方程为：

对于数组中的每个元素a[k]，如果j>=a[k]并且Q[i-1,j-a[k]]=1,那么Q[i,j]=1. 初始条件为Q[0,0]=1,其它都为0，最终我们只要从后（i=n,j=SUM/2）往前逐层遍历这个矩阵Q,找到第一个不为0的像，那么SUM-j-j(min|S1-S2|)即为所求.代码如下：（数组下标从1开始计算）

void array_partition_solve_noBounds(int *a,int n){

//首先对数组元素求和

int SUM=0;

for(int i=1;i<=n;i++){

SUM+=a[i];

}

//初始化

int **Q=new int*[n+1];

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

Q[i]=new int[SUM/2+1]();

}

Q[0][0]=1;

//递推求解

for(int k=1;k<=n;k++){

for(int i=k;i>=1;i--){

for(int j=a[k];j<=SUM/2;j++){

if(Q[i-1][j-a[k]])

Q[i][j]=1;

}

}

}

cout<<"最小差值为:"<<ends;

int j=SUM/2;

bool tag=0;

int index_i=0;

int index_j=0;

for(;j>=0;j--){

if(tag)

break;

int i=n;

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

//是否存在一个i使得和为j

if(Q[i][j]){

cout<<SUM-j-j<<endl;

tag=1;

index_i=i;

index_j=j; //记录相应的下标，以便打印出结果

break;

}

}

}

cout<<"其中一个集合元素为:"<<ends;

while(index_j>0){

for(int k=1;k<=n;k++){

if(index_j>=a[k] && Q[index_i-1][index_j-a[k]]){

cout<<a[k]<<" "<<ends;

index_i--;

index_j-=a[k];

break;

}

}

}

//free mem

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

delete [] Q[i];

}

delete [] Q;

}

时间代价为O( SUM* n^2)

问题的变种：在原问题变为大小为2*n的数组，要求A1和A2都包含n个元素，那么如何划分使得|S1-S2|最小。

分析：和原问题一样，只不过我们这里限定状态Q[i,j]中的i的取值最大为n，最终只需要遍历Q[n,j] j=SUM/2 to 0,中第一个不为0的项输出SUM-j-j (min|S1-S2|) 即可，代码如下：

/*

给定一个大小为2n正整数数组a，将其划分成两个大小为n的两个数组a1和a2，S1为a1中元素求和，S2为a2中元素的和，使得S1-S2最小

分析：假设数组a的综合为SUM,那么如果S1=SUM/2，这就是最好的一种划分，那么我们就要是S1尽量接近SUM/2，这样最终的结果就是最优的

用Q[i,j]表示是否存在i个元素，使得他们的和为j, 0=<i<=n, 0=<j<=SUM/2，(如果存在Q[i,j]=1,否则为0)那么状态转移方程为：

Q[i,j]=1  if Q[i-1,j-a[k]]=1 && j>=a[k]    (1=<k<=2*n)

初始化Q[i][j]=0 for all 0=<i<=n  0=<j<=SUM/2, Q[0,0]=1;

*/

void array_partition_solve(int *a,int n){

//先求数组a的和

int SUM=0;

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

SUM+=a[i];

}

int **Q=new int*[n+1];

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

Q[i]=new int[SUM/2+1]();

}

Q[0][0]=1;

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

int i=k<n?k:n;

for(;i>=1;i--){

//for(int j=1;j<=SUM/2;j++){

// if(j>=a[k] && Q[i-1][j-a[k]])

for(int j=a[k];j<=SUM/2;j++){//小优化

if(Q[i-1][j-a[k]])

Q[i][j]=1;

}

}

}

cout<<"最小差值为:"<<ends;

int i=n;

int j=SUM/2;

while(j>=0){

if(Q[i][j]){

cout<<SUM-j-j<<endl;

break;

}

j--;

}

cout<<"其中一个集合元素为:"<<ends;

i=n;

j=SUM/2;

while(j>0){

if(Q[i][j]){

int k=1;

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

if(j>=a[k] && Q[i-1][j-a[k]])

break;

}

cout<<a[k]<<" "<<ends;

i--;

j=j-a[k];

}else{

j--;

}

}

//free mem

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

delete [] Q[i];

}

delete [] Q;

}

时间代价为O(SUM*n^2)

关于这个题目的其它解法，还可以参考： http://blog.csdn.net/wumuzi520/article/details/7028705

问题的进一步扩展，如果原始数组中存在负数怎么办？

那么我们可以对数组进行预处理，给每个元素加上其中最大的那个负数的绝对值A，这样这个数组就成为一个正数的数组，那么利用上面的解法来求即可，只需要最后打印其中某个集合时候，要对每个元素再减去A。（这个题目是针对两个集合都是n个元素，原始数组是2*n个元素的变种。）