一个数值中有若干正整数，将此数组划分为两个子数组，使得两个数组各元素之和a,b的差最小(12年上交CS复试题)，大家怎么看呢.....

我觉得这是一个0-1背包问题，背包体积是总和的一半。

sort A[1...n]        
// Now A[1] >= A[2] >= ... A[n]

Array A1[]  // 记录一部分
Array A2[]  // 记录另一部分

sum_1 = 0
sum_2 = 0

j = k = 1

for(i = 1 ; i <= n ; i++)
{
  if(sum_1 < sum_2)
  {
     A1[j++] = i
     sum_1 += A
  }
  else
  {
     A2[k++] = i
     sum_2  += A
  }
}

while(--j)
print(A[A1[j]])  // 打印结果

while(--k)
print(A[A2[k]])  // 打印结果

没试验~~不知道靠不靠谱.
第一感觉就是 排序然后 两个变量记录两个部分的和，如果哪一部分小就把剩余元素中最大的并到小的那个部分里。。如此循环

X1n4n 发表于 2013-1-21 17:05
sort A[1...n]        
// Now A[1] >= A[2] >= ... A[n]

当时坐在考场里我和你的想法一样的，事实证明这是不行滴，再加上读取文件名出了问题，然后感谢科大海涵地收留了我，一个学期过去了，我的算法还是这么弱，我相信软院里肯定有高手能解决，yel_hb是九度排行前五的牛人，望高人现身，给个完整代码，小菜在此表示衷心感谢

先求总和，再排序。
然后选元素到一个组里，直到这个组的和等于或接近于1/2总和。剩下的元素放一组

额...不是牛人的飘过...
随机取了6个数试了一下，先用DP求最大值，然后返回去构造选入的数，比较凌乱=_=!。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <minmax.h>
using namespace std;

int main()
{
        int iput[6];
        int i, j, v, n, sum;
        int *f;
        srand(time(NULL));

        sum = 0;
        for ( i = 0; i < 6; ++i )
        {
                iput[i] = rand() % 100 ;
                sum += iput[i];
                printf( "%d ", iput[i] );
        }
        printf( "\n" );
        
        sort( iput, iput + 6 );
        
        n = sum / 2;
        f = new int[n + 1];
        memset( f, 0, sizeof(int) * ( n + 1));

        for ( i = 0; i < 6; ++i )
                for ( v = n; v >= iput[i]; --v )
                        f[v] = max ( f[v], f[v - iput[i]] + iput[i] );
        
        j = f[n];
        for ( i = 5; i >= 0; --i )
        {
                if( f[j] == f[j - iput[i]] + iput[i] )        
                {
                        printf("%d ", iput[i] );
                        j -= iput[i];
                }
        }
        
        printf( "\n%d\n", sum - 2 * f[n] );

        return 0;
}

把所有可能的N（N-1）个两个数的差求出来，排序，从最大的一对开始放

夜花烛 发表于 2013-1-21 18:58
把所有可能的N（N-1）个两个数的差求出来，排序，从最大的一对开始放

不对，差最小的那几对可能之前被占用了。那只能先随机分组，然后去找差小于总体的差的那一对，交换

多谢yel_hb黄大哥，了却我一桩心事，不喜欢膜拜额，这也是天天刷ACM刷出来的实力，术业有专攻，在算法方面强我太多，我擦，技不如人的地方太多了