[讨论]讨论一下这个题的算法.......

惠儿雨点

输入十个数(int型)， 把这十个数分两组A和B，A组数的和为sum1，B组数的和为sum2，问怎样分，可使sum1和sum2相差最小。
讨论一下解题思路。


比如：


90 25 65 30 58 268
70 28 60 40 55 253 差15


90 25 60 30 55 260
70 28 65 40 58 261 差１

唏唏鉿鉿HJP

嗯，上次听讲座，Topcoder的副总裁考过的好像就是这题，小弟差劲，听不明白。

love戒情人

我有一种想法，不知道是否正确：
按顺序找出每整数及其相差绝对值最小的整数，让它们配对。
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#define MAX 10
#define GREATEST 858993460
typedef struct
{
int elem;
bool used;
}Number;

void Choose(Number *num, int *agroup, int *bgroup)
{
int n = 0,a = 0, b = 0;
int finish = 0;
int compare;
int id;
int length = MAX;
int halfLength = length/2;
do
{
if(!num[n].used)
{
num[n].used = true;
compare = GREATEST;
agroup[a] = num[n].elem;
a++;
for(int i = n + 1; i < length; i++)
{
int com = num[n].elem - num[i].elem;
com = (com < 0)?(-com):com;
if(compare > com)
{
compare = com;
id = i;
}
}
num[id].used = true;
bgroup[b] = num[id].elem;
b++;
}
n++;
finish++;
}
while(finish <= halfLength);
}
void main()
{
Number *num = new Number[MAX];
int *a = new int[MAX/2];
int *b = new int[MAX/2];
srand( (unsigned) time(NULL));
for(int i = 0; i < MAX; i++)
{
num[i].elem = rand()%100;
num[i].used = false;
}
Choose(num, a, b);
cout<<"the result is:"<<endl;
cout<<"a : ";
for(i = 0; i < MAX/2; i++)
cout<<" "<<a[i]<<" ";
cout<<endl<<"b : ";
for(i = 0; i < MAX/2; i++)
cout<<" "<<b[i]<<" ";
}

海的无奈

不好意思， 我做错了。

罗ぷ曼ㄉ帝Ke

我有另一种想法，不知道是否正确，举个例子吧：
设有一列整数： 8 7 12 16 4 9 3 1 5 20
1： 先把它排序得：1 3 4 5 7 8 9 12 16 20
2：
分组：（下标为偶数的分为一组，其它的为另一组）
a组： 1 4 7 9 16
b组： 3 5 8 12 20
3：
求出a，b组对应元素的差的绝对值：
list： 2 1 1 3 4
4：求得 绝对值之和的一半 half ＝ （2 + 1 +1 +3+4)/2 = 5.5
5: 穷举找出最接近 half的一组 2，3 （另一组就是 1，1，4）
6：用 2， 3 所对应的下标（0 和 3）交换 a组 和 b组的值。
交换后得：
a 组：3 4 7 12 16 （总和为: 42)
b组：1 5 8 9 20 (总和为: 43)

最ヅ后愛上你

看看我的算法
我想的是先排序 然后比较差值大小
1 3 4 5 7 8 9 12 16 20
a=1,b=3
比较abs((a+4)-(b+5))和abs((a+5)-(b+4))那个值小 ；就那两个相加 这里是 :
a+5=6 ;1 5
b+4=7 ;3 4
比较abs((a+7)-(b+8))和abs((a+8)-(b+7))那个值小 ；就那两个相加 这里是 :
a+8=14 ;1 5 8
b+7=14 ;3 4 7
后面的循环。。。。。。。。。。。。。

爱虎老油♂

不知道的我想法怎么样，大家不要见笑
以知道
a b c d f g h j k l
1：先求每个数与他们平均数的差值
A B C D F G H J K L
2:现在的问题变成求在上面中选择N/2个数，使他们的和的绝对值MIN

3:下面进行判断，有多少个是正的，多少是负的
（1）个数一样。。。。。。
（2）正的个数（m）比负的个数（n）多，那就我们就选择负数的那一组，在选择m+n/2-m个的正数中最大的，就是其中一组（所有的正数+(m+n)/2负数是大于等于0的）
（3）负的个数比正的个数多，如（2）

森林的眼泪

7楼的算法可以改进一下:
1.排序
1 3 4 5 7 8 9 12 16 20
2.将这10个数分为两组，必然每组5个，数组命名为A,B;
从后往前：
（第一次不必考虑顺序)
A： 20
B： 16
sum(A)>sum(B); 12给B，9给A；
A: 20 9
B: 16 12
sum(A)>sum(B); 9->B,8->A;
A: 20 9 8
B: 16 12 7
sum(A)=sum(B); 任意；
A: 20 9 8 5
B: 16 12 7 4
sum(A)>sum(B);1->A,3->B;
A:20 9 8 5 1
B:16 12 7 4 3
完成！

尐妖

9楼的做法比较简捷，不过我觉得这样做（类似贪心算法），得出的结过有可能不是最优解(即 |A组- B组|不是最小值）。

優雅dē颓废

垃圾代码 凑合这看吧
#include<iostream.h>
#include<math.h>
void f1(int a[])/*排序*/
{
for(int i=0;i<10;i++)
for(int j=i;j<10;j++)
if(a[i]>a[j+1]){int temp=a[i];a[i]=a[j+1];a[j+1]=temp;}
}
main()
{
int a[10],A[5],B[5],p1=0,p2=0,x=0,i;
for(i=0;i<10;i++)
cin>>a[i];
f1(&a[0]);
for(i=0;i<10;i=i+2)
if(abs((p1+a[i])-(p2+a[i+1]))<=abs((p1+a[i+1])-(p2+a[i])))/*比较差值大小*/
{p1=p1+a[i];p2=p2+a[i+1];A[x]=a[i];B[x++]=a[i+1];}/*进行赋值*/
else
{p1=p1+a[i+1];p2=p2+a[i];A[x]=a[i+1];B[x++]=a[i];}/*进行赋值*/
for(i=0;i<5;i++)/*输出*/
cout<<A[i]<<' ';
cout<<p1<<"\n";
for(i=0;i<5;i++)
cout<<B[i]<<' ';
cout<<p2<<"\n";
}