今天面试栽在这个小题上了

imkuang

原帖由 heefly 于 2008-3-4 18:22 发表
先排序，由重到轻。V10，V9，V8......V1

左边放V10，右边放V9，
根据轻的一边来放V8，这样就是3个球如何放得以两边差最小。
再根据轻的一边来放V7，这样就是4个球如何放得意两边的茶最小。
同样 5个，6个 ...

这样不能保证每有是5个球，极端情况下，可能出现一边只有一个球，另一边九个球的情况。

wildlily980

这个题我想了三个小时也没有想出来。——十分地郁闷啊。
不过肯定第一步把最大的和第二大的分开放是不行的。例如下面这组数字，我们把题目简化了一下，成为六个数字。
9,8,7,7,6,1

应该是9+8+1=18;
         7+7+6=20;
第一大的9和第二大的8不应该分开。

[ 本帖最后由 wildlily980 于 2008-3-6 16:26 编辑 ]

cugb_cat

原帖由 wildlily980 于 2008-3-6 16:25 发表
这个题我想了三个小时也没有想出来。——十分地郁闷啊。
不过肯定第一步把最大的和第二大的分开放是不行的。例如下面这组数字，我们把题目简化了一下，成为六个数字。
9,8,7,7,6,1

应该是9+8+1=18;
      ...

怎样放都有不行的时候，所以要穷举。

crashsky

把10个球从大到小排序放上去
现放最大的，下一个球时那边翘起来就放到那边
这是最佳答案。 曾经做过上万个数字分组这种方式是差别最小的

cugb_cat

原帖由 crashsky 于 2008-3-6 17:17 发表
把10个球从大到小排序放上去
现放最大的，下一个球时那边翘起来就放到那边
这是最佳答案。 曾经做过上万个数字分组这种方式是差别最小的

10个球的重量分别为1,2,3,4,5,6,7,8,9,10时这种方法就不行。

icylord

搜索 反正才10个球··
如果要有效率则加个数组标记来剪枝

kktall

74楼 发表于 2008-3-6 17:17   
把10个球从大到小排序放上去
现放最大的，下一个球时那边翘起来就放到那边
这是最佳答案。 曾经做过上万个数字分组这种方式是差别最小的


--------
10个数字的,仍旧可以的啊,

10,7,5,4,1
9,8,6,3,2

yang_java2004

原帖由 benjiam 于 2008-3-3 17:56 发表
应该是1：1 比较 分成 轻重2堆。
然后2堆分别排序， 然后合成一个列。
合成不是简单的加在一起， 不断拿最那堆和 重堆里面最轻的比较，类似冒泡的算法

在一个队列以后
那就是
先左10  右边9
不断向轻那 ...

听听我的想法：

天平两边称为 A        B

一边放一个.（假设A边轻）

然后从剩下的8个中找出一个,放入A 致使A边重 ,然后加B 使B重

依次放置！



貌似不够严谨！

bugboy_bugboy

我觉得没有准确测量工具的情况下，只有算次优算法。因为无法验证这个解。：）

sunnyfun

既然要求两边球的数量相同，那就很简单，之前已经有人想到了：
先按重量排序，按总量大小编号为1~10，然后单数放左边，双数放右边，OK
放5个使两边质量之差最小，就是求他们的算术平均的过程
假设每个球重量大小依次为 X1 到 X10
那么可以这么放：
X1    X10
X9    X2
X3    X8
X7    X4
X5    X6

可以发现正好单数在一边，双数在另一边