[12年上交CS复试题]一道算法设计题..........
一个数值中有若干正整数，将此数组划分为两个子数组，使得两个数组各元素之和a,b的差最小(12年上交CS复试题)，大家怎么看呢..... 我觉得这是一个0-1背包问题，背包体积是总和的一半。 本帖最后由 X1n4n 于 2013-1-21 17:09 编辑sort A
// Now A >= A >= ... A
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 = i
sum_1 += A
}
else
{
A2 = i
sum_2+= A
}
}
while(--j)
print(A])// 打印结果
while(--k)
print(A])// 打印结果
没试验~~不知道靠不靠谱.
第一感觉就是 排序然后 两个变量记录两个部分的和，如果哪一部分小就把剩余元素中最大的并到小的那个部分里。。如此循环 X1n4n 发表于 2013-1-21 17:05 static/image/common/back.gif
sort A
// Now A >= A >= ... A
当时坐在考场里我和你的想法一样的，事实证明这是不行滴，再加上读取文件名出了问题，然后感谢科大海涵地收留了我，一个学期过去了，我的算法还是这么弱，我相信软院里肯定有高手能解决，yel_hb是九度排行前五的牛人，望高人现身，给个完整代码，小菜在此表示衷心感谢 先求总和，再排序。
然后选元素到一个组里，直到这个组的和等于或接近于1/2总和。剩下的元素放一组 本帖最后由 yel_hb 于 2013-1-21 19:38 编辑
额...不是牛人的飘过...
随机取了6个数试了一下，先用DP求最大值，然后返回去构造选入的数，比较凌乱=_=!。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <minmax.h>
using namespace std;
int main()
{
int iput;
int i, j, v, n, sum;
int *f;
srand(time(NULL));
sum = 0;
for ( i = 0; i < 6; ++i )
{
iput = rand() % 100 ;
sum += iput;
printf( "%d ", iput );
}
printf( "\n" );
sort( iput, iput + 6 );
n = sum / 2;
f = new int;
memset( f, 0, sizeof(int) * ( n + 1));
for ( i = 0; i < 6; ++i )
for ( v = n; v >= iput; --v )
f = max ( f, f] + iput );
j = f;
for ( i = 5; i >= 0; --i )
{
if( f == f] + iput )
{
printf("%d ", iput );
j -= iput;
}
}
printf( "\n%d\n", sum - 2 * f );
return 0;
}
把所有可能的N（N-1）个两个数的差求出来，排序，从最大的一对开始放 夜花烛 发表于 2013-1-21 18:58 static/image/common/back.gif
把所有可能的N（N-1）个两个数的差求出来，排序，从最大的一对开始放
不对，差最小的那几对可能之前被占用了。那只能先随机分组，然后去找差小于总体的差的那一对，交换 多谢yel_hb黄大哥，了却我一桩心事，不喜欢膜拜额，这也是天天刷ACM刷出来的实力，术业有专攻，在算法方面强我太多，我擦，技不如人的地方太多了
页:
[1]