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

heefly

先排序，由重到轻。V10，V9，V8......V1

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

yvtianzll

原帖由 benjiam 于 2008-3-4 17:26 发表



你对我的算法理解有问题。  如果一边的重量超过了另一边 就要转向的。

  1 2 3 4 5 已经比10 重了

所以 应该是
10                5

10                5 +4

10                5+4 +3
1 ...

假如有6个小球，质量为1，4，5，6，7，8？？

shmilylxx

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

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

这种办法，振荡确实是收敛的，能找出“比较优”的方案~
但是不能证明该法最优。

NalaGinrut

原帖由 benjiam 于 2008-3-4 17:26 发表



你对我的算法理解有问题。  如果一边的重量超过了另一边 就要转向的。

  1 2 3 4 5 已经比10 重了

所以 应该是
10                5

10                5 +4

10                5+4 +3
1 ...

我没理解错
1 2 3 4并没有大于10
在这个时候刚好相等，如果你决定加右边，那铁定错
如果加左边，就是我说的那种情况

benjiam

假如有6个小球，质量为1，4，5，6，7，8？？

8                            7
8                          7+6
8+5                     7+6
4+5+8                 7+6+1

相差为2

最佳的算法是 4+5+6   7+8+1
但是这个算法 用天平是算不出来的。
因为一旦最后的1 是 2 、3  就又会进化到最优秀的结果了。

NalaGinrut

原帖由 benjiam 于 2008-3-4 21:16 发表
假如有6个小球，质量为1，4，5，6，7，8？？

8                            7
8                          7+6
8+5                     7+6
4+5+8                 7+6+1

相差为2

最佳的算法是 4+ ...

你的想法是没问题的，但是你究竟用什么办法来获得精确排序的？
在天平没有刻度，而你又没有穷举的情况下，这个前提能够成立吗？

benjiam

没有啊

我先排序啊
你去仔细看看。  先按照2组 然后按轻到重排成一个队列。 这是可以办到的 类似冒泡排序。

benjiam

原帖由 NalaGinrut 于 2008-3-4 20:42 发表



我没理解错
1 2 3 4并没有大于10
在这个时候刚好相等，如果你决定加右边，那铁定错
如果加左边，就是我说的那种情况

.....

如果是1 2 3 4  10 的话

那就是
10    4+3+2+1

后面随便放哪里  反正都比1 小。然后继续按照这个算法往下加

NalaGinrut

原帖由 benjiam 于 2008-3-4 21:27 发表


.....

如果是1 2 3 4  10 的话

那就是
10    4+3+2+1

后面随便放哪里  反正都比1 小。然后继续按照这个算法往下加

比1小？按你的意思1是最轻的，比1小是什么?
你用的应该是类似于merge方法，只不过你把最后的归并和称量判断合在一起了，
在这种情况下，下一个最轻的只能是5了，你说随便放哪边，那放右边是不是我说的那种情况？

ctqucl

冒泡排序先，奇偶交叉放
然后从轻球交换起
奇数（轻）边反转之时，便是临界位置，此时两种排列选两边球序号相加之差小的一种排列。