一、数组分割问题:(原帖见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;
}
}
今天又看见了这个题目,好像上次是李灾跟我说腾讯面他的时候问了这个问题的。想了半天,在网上也看了半天,发现一个不错的算法,先帖出来:^ ^
/*
有两个数组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 ;
}
分享到:
相关推荐
2交换两个数组的值,使交换之后差值最小.py
求数组交换和差最小,c#实现关键代码展示,需要的看看,或许对你有些帮助。
这篇文章主要介绍了JS合并两个数组的3种方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 需要将两个数组合并成为一个的情况。比如: var a = [1,2,3];...
用C语言编写两个数组合并成一个数组,并有序排列 。数组合并。
【输出形式】程序将两个有序一维数组合并为一个有序数组并按照从小到大顺序输出。每个元素输出时用空格分隔,最后一个输出之后没有空格。 【样例输入】 6 2 5 8 11 20 35 4 1 6 15 60 【样例输出】1 2 5 6 8 11 15 ...
有两个数组a,b,大小都为n,数组元素的值任意,无序 //要求:通过交换a,b中的元素,使数组a的元素之和与数组b的元素之和之间//的差最小?
该源代码很好地体现了数组与List之间的转换,同时也体现了两个集合的合并操作
C# 将两个整型数组的元素相加。别忘给评分!
网上那种找出两个数组重复元素的代码复杂度较高,这个比较简单,一次循环搞定
C语言程序设计-输入一维数组的8个元素,并将最大值与最后一个数交换,最小值与第一个数交换,然后输出交换后的8个数。
最终我将一个数组平分成两个小数组,分别求出各数组的两个最大及两个最小值,然后再分别组合4个最大值和四个最小值,最后再比较出大小,得出4个最大值的两个大值,4个最小值数组的两个最小值!不知道是不是分治法,...
检查数组2中是否包含数组1中的所有元素.个人上课的作业。仅供参考。
分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法
获取两个数组相同的元素或不同的元素输出,使用java自带函数compare比较,或二分比较来取值,
比较json对象中的两个数组含有的相同元素,点击按钮输出新的数组
给定两个整型数组,本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组,每行先给出正整数N(≤20),随后是N个整数,其间以空格分隔。 输出格式: 在一行中按照数字给出的...
判断两个数组所含元素是否相同,数量也要相同。
编写程序,将一个包含20个元素的数组STRING分成一个偶数数组STRING1和一个奇数数组STRING2。 要求采用循环和串操作指令完成。
求一个数组的两个最小数,并返回下标。在数组中查找最小的两个数的下标。
递归求数组最大最小元素。