`
duoerbasilu
  • 浏览: 1474538 次
文章分类
社区版块
存档分类
最新评论

数组分割问题(另一种说法是交换两个数组元素使两个数组和的差最小)

 
阅读更多

一、数组分割问题:(原帖见http://www.cppblog.com/baby-fly/archive/2009/09/24/92392.html

题目概述:有一个没有排序,元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组,并使两个子数组的和最接近。
假设数组A[1..2N]所有元素的和是SUM。模仿动态规划解0-1背包问题的策略,令S(k, i)表示前k个元素中任意i个元素的和的集合。显然:
S(k, 1) = {A[i] | 1<= i <= k}
S(k, k) = {A[1]+A[2]+…+A[k]}
S(k, i) = S(k-1, i) U {A[k] + x | x属于S(k-1, i-1) }
按照这个递推公式来计算,最后找出集合S(2N, N)中与SUM最接近的那个和,这便是答案。这个算法的时间复杂度是O(22N).
因为这个过程中只关注和不大于SUM/2的那个子数组的和。所以集合中重复的和以及大于SUM/2的和都是没有意义的。把这些没有意义的和剔除掉,剩下的有意义的和的个数最多就是SUM/2个。所以,我们不需要记录S(2N,N)中都有哪些和,只需要从SUM/2到1遍历一次,逐个询问这个值是不是在S(2N,N)中出现,第一个出现的值就是答案。我们的程序不需要按照上述递推公式计算每个集合,只需要为每个集合设一个标志数组,标记SUM/2到1这个区间中的哪些值可以被计算出来。关键代码如下:

for(i = 0; i < N+1; i++)
for(j = 0; j < sum/2+1; j++)
flag[i][j] = false;
flag[0][0] = true;
for(int k = 1; k <= 2*N; k++) {
for(i = k > N ? N : k; i >= 1; i--) {
//两层外循环是遍历集合S(k,i)
for(j = 0; j <= sum/2; j++) {
if(j >= A[k] && flag[i-1][j-A[k]])
flag[i][j] = true;
}
}
}
for(i = sum/2; i >= 0; i--) {
if(flag[N][i]) {
cout << "minimum delta is " << abs(2*i - sum) << endl;
break;
}
}
二、交换两个数组元素使两个数组和的差最小:(http://blog.csdn.net/kittyjie/archive/2009/07/28/4386742.aspx)

今天又看见了这个题目,好像上次是李灾跟我说腾讯面他的时候问了这个问题的。想了半天,在网上也看了半天,发现一个不错的算法,先帖出来:^ ^

/*

有两个数组a,b,大小都为n,数组元素的值任意整形数,无序;
要求:通过交换a,b中的元素,使[数组a元素的和]与[数组b元素的和]之间的差最小。

*/

/*
求解思路:

当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后,a和b的和之差为
A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
设x = a[i] - b[j]

|A| - |A'| = |A| - |A-2x|

假设A > 0,

当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,

如果找不到在(0,A)之间的x,则当前的a和b就是答案。

所以算法大概如下:

在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。

*/

把算法大概实现了一下,程序如下:

int test( float a[], float b[], int n)
{
float sumA, sumB; // sumA为数组a总和,sumB为数组b总和
float sum_diff, num_diff; // sum_diff为a,b总和差, num_diff为a,b中各选的两个数之差
float temp1, temp2; // temp1为 每轮sum_diff/2, temp2为每轮所选两个数之差于temp1最接近的那个
int i, j;
float temp; // 用于对调a,b间数
int tempi, tempj; // 每轮所选两个数之差于temp1最接近的那组数
unsigned int flag_sum = 0 , flag_num = 0 ; // flag_sum为1, sumA大于sumB; flag_num为1, 此轮存在两个数之差小于sum_diff




while ( 1 ){

// 算出a,b数组和
sumA = 0 ;
sumB = 0 ;
for (i = 0 ;i < n;i ++ )
{
sumA += a[i];
sumB += b[i];
}

if (sumA >= sumB){
sum_diff = sumA - sumB;
flag_sum = 1 ;
}
else
sum_diff = sumB - sumA;

temp1 = sum_diff / 2 ;
temp2 = temp1;
tempi = 0 ;
tempj = 0 ;

// 找出a,b间差值最接近sum_diff/2的那一对数
if (flag_sum == 1 ){ // sumA > sumB
for (i = 0 ; i < n; i ++ )
for (j = 0 ; j < n; j ++ )

if (a[i] > b[j]){
num_diff = a[i] - b[j];
if (num_diff < sum_diff){
flag_num = 1 ;
if (num_diff >= temp1){
if (num_diff - temp1 < temp2){
temp2 = num_diff - temp1;
tempi = i;
tempj = j;
}
}
else {
if (temp1 - num_diff < temp2){
temp2 = temp1 - num_diff;
tempi = i;
tempj = j;
}
}
}
}
}
else {
for (i = 0 ; i < n; i ++ )
for (j = 0 ; j < n; j ++ )

if (a[i] < b[j]){
num_diff = b[j] - a[i];
if (num_diff < sum_diff){
flag_num = 1 ;
if (num_diff >= temp1){
if (num_diff - temp1 < temp2){
temp2 = num_diff - temp1;
tempi = i;
tempj = j;
}
}
else {
if (temp1 - num_diff < temp2){
temp2 = temp1 - num_diff;
tempi = i;
tempj = j;
}
}
}
}
}

if (flag_num == 0 )
break ;

temp = a[tempi];
a[tempi] = b[tempj];
b[tempj] = temp;

flag_num = 0 ;
flag_sum = 0 ;
}

for (i = 0 ; i < n;i ++ )
printf( " %f/t " ,a[i]);

printf( " /n " );

for (i = 0 ; i < n;i ++ )
printf( " %f/t " ,b[i]);

printf( " /n " );

return 0 ;
}

int main( int argc, char * argv[])
{

float a[ 3 ] = { 4 , 5 , 12 };
float b[ 3 ] = { 1 , 2 , 3 };

test(a, b, 3 );

return 0 ;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics