标题:[讨论]讨论一下这个题的算法.......
只看楼主
谁与争疯
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:海南省
等 级:版主
威 望:188
帖 子:15070
专家分:17503
注 册:2007-4-22
结帖率:96.79%
 问题点数:0 回复次数:29 
[讨论]讨论一下这个题的算法.......

输入十个数(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 差1

搜索更多相关主题的帖子: 算法 int 思路 解题 
2007-05-17 22:54
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 
嗯,上次听讲座,Topcoder的副总裁考过的好像就是这题,小弟差劲,听不明白。

人生重要的不是所站的位置,而是所朝的方向
2007-05-18 01:22
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 

我有一种想法,不知道是否正确:
按顺序找出每整数及其相差绝对值最小的整数,让它们配对。
#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]<<" ";
}


人生重要的不是所站的位置,而是所朝的方向
2007-05-18 03:37
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 
不好意思, 我做错了。

人生重要的不是所站的位置,而是所朝的方向
2007-05-18 12:00
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 
我有另一种想法,不知道是否正确,举个例子吧:
设有一列整数: 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)


人生重要的不是所站的位置,而是所朝的方向
2007-05-18 12:29
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
得分:0 

看看我的算法
我想的是先排序 然后比较差值大小
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
后面的循环。。。。。。。。。。。。。


羊肉串 葡萄干 哈密瓜!!
2007-05-18 19:31
痴情绝对
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2007-5-17
得分:0 
不知道的我想法怎么样,大家不要见笑
以知道
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)
2007-05-18 20:54
Arcticanimal
Rank: 3Rank: 3
等 级:论坛游民
威 望:7
帖 子:341
专家分:20
注 册:2007-3-17
得分:0 
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
完成!

try new catch
2007-05-18 21:41
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
得分:0 
9楼的做法比较简捷,不过我觉得这样做(类似贪心算法),得出的结过有可能不是最优解(即 |A组- B组|不是最小值)。

人生重要的不是所站的位置,而是所朝的方向
2007-05-18 22:04
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
得分:0 

垃圾代码 凑合这看吧
#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";
}


羊肉串 葡萄干 哈密瓜!!
2007-05-19 11:52



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-140310-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.459551 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved