注册 登录
编程论坛 → C++教室

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

谁与争疯 发布于 2007-05-17 22:54， 1844 次点击

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

29 回复
#2
herbert_19872007-05-18 01:22
嗯，上次听讲座，Topcoder的副总裁考过的好像就是这题，小弟差劲，听不明白。
#3
herbert_19872007-05-18 03:37

我有一种想法，不知道是否正确：
按顺序找出每整数及其相差绝对值最小的整数，让它们配对。
#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]<<" ";
}
#4
herbert_19872007-05-18 12:00
不好意思， 我做错了。
#5
herbert_19872007-05-18 12:29
我有另一种想法，不知道是否正确，举个例子吧：
设有一列整数： 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)
#6
mp3aaa2007-05-18 19:31

看看我的算法
我想的是先排序 然后比较差值大小
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
后面的循环。。。。。。。。。。。。。
#7
痴情绝对2007-05-18 20:54
不知道的我想法怎么样，大家不要见笑
以知道
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）
#8
Arcticanimal2007-05-18 21:41
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
herbert_19872007-05-18 22:04
9楼的做法比较简捷，不过我觉得这样做（类似贪心算法），得出的结过有可能不是最优解(即 |A组- B组|不是最小值）。
#10
mp3aaa2007-05-19 11:52

垃圾代码 凑合这看吧
#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";
}
#11
herbert_19872007-05-19 15:28
11楼的够简捷，不过还是那个问题，在某些情况下不能得到最优解，比如：
输入一窜整数：1 4 5 8 9 13 14 17 22 27
运行结果是：
（a组） 1 8 9 17 27 62(总和）
（b组）4 5 13 14 22 58（总和）
但其实最优解为：
（a组） 1 5 14 13 27 60(总和）
（b组） 4 8 17 9 22 60（总和）
#12
jiangzw6252007-05-19 17:48
已经差不多了阿。再加一步就可以。
另偶数组为A,奇数组为B
当数组元素个数为偶数
因为两个数组都是有序的。并且A[i]>=B[i]
所以sum(A)>=sum(B)
而且每个数组不管是什么数，都可以成为有序的。
所以A[i]可以与B[i]交换,这样sum(A)减少,sum(B)增大
并保证仍然有序
可以得到最优解。
否则
先忽略B[0],这时B[i]>=A[i]
与上面的情况恰恰相反，但这时要比较的是
(sum(B)与sum(A)的绝对值-B[0])最小值.
同样可得到最优解
#13
北冥鸟2007-05-19 18:25

可不可以先把所有的数字由小到大或者由大到小排列好，
将这些数字放到数组中。
然后第一个和最后一个，第二个和倒数第二个组合，
这样将数字分成两组，sum1 sum2
这样就可以把它们的差算出且最小！
#14
谁与争疯2007-05-19 21:37
十个int型的数，是由用户输入的，数的大小都不固定！如果14楼这样分的话，那就
#15
leeco2007-05-20 01:28
SUM/2的0-1背包问题。已知是整数的话可以用动态规划，不是整数就DFS。
#16
谁与争疯2007-05-20 08:30
头晕，是不是运用了数据结构的问题？还没有学到数据结构。
#17
lishixiong2007-05-20 10:28

我的一点想法：

1.先输入10个数到x[]中。
2.任取一个放入a[]中，然后在x[]中剩余的9个数中寻找与a[1]差值最小的元素放入b[1]中。
3.利用循环计算a[]，b[]数组所有元素之和，求出差值再在x[]中剩余的元素中寻 找与差值最接近的元素，放入和较小的一组数组中。
4.以此方法直到赋完x[]中所有的元素。

此题得解。
#18
herbert_19872007-05-20 12:44
16楼 那为高手，能不能详细一点解释一下，什么是“动态规划”？为什么当 SUM/2 不是整数时就用DFS（深度优先是吗？）？
#19
leeco2007-05-20 14:54
已知若干物品的大小，以及一个背包容量，物品不能分割，求此背包所能装载的最大物品总大小的问题，named 0-1背包问题。
更一般的形式是，已知若干物品的大小和价值，以及一个背包的容量，物品不能分割，求此背包作能装载的最大物品价值总和。

把这道题目的每个数看作一个物品大小，物品总大小记为SUM，背包容量SUM/2，求解这个背包问题就可以把数分为两个部分，装在背包里的部分，和没装在背包里的部分，这两部分的差值是最小的。

而背包问题的解法在许多算法书中都有详细讨论，我不在此详述
#20
amdam230002007-05-20 19:30

十四楼的不可行啊~~~
#21
herbert_19872007-05-20 19:46
嗯，我明白了，谢谢leeco！
#22
谁与争疯2007-05-20 19:50
经20楼的讲解，茅塞顿开啊。
#23
谁与争疯2007-05-20 19:51
有哪位能编个程序出来 瞧一瞧吗？
#24
痴情绝对2007-05-20 22:30
24的好懒啊....
#25
谁与争疯2007-05-21 00:19
我这不是不懂编么。居然说我懒~~好伤心啊！
#26
北冥鸟2007-05-21 19:11

即使是用户随即输入的10个数或者100个数,这没关系啊!
只须加一个排序的语句就好了!
排好序之后就可以接着我之前那样做了!
#27
谁与争疯2007-05-21 23:15
我倒是觉得 18楼 的算法、比你的算法，好很多很多！

而且、你的算法、漏洞总觉得还有很多的很多。按你这样排序下来、然后对称调换、不行D，不行D。

还是那句老话、有哪位高手能把 程序 写出来看看吗？
#28
谁与争疯2007-05-21 23:16
再次声明~~我不懒！只是不懂么！
#29
痴情绝对2007-05-22 08:45

去试着编,说不定有灵感哦
1
©2025, BC-CN.NET
电脑版