智游城

 找回密码
 注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 416|回复: 13

选西瓜

[复制链接]
老陈 发表于 2019-10-30 03:31:10 来自手机 | 显示全部楼层 |阅读模式
有N(很多)个西瓜,让你选一个。规则是,拿来一个西瓜,你可以选中,此时选西瓜结束,如果你拒绝这个西瓜,再拿一个西瓜让你选,重复第一个的办法。拿来一个西瓜让你选时你无法知道后面西瓜的大小,可以知道还有多少个西瓜。显然随便选一个,选中最大的西瓜的概率为1/N,采用什么策略可以提高选中最大西瓜的概率?
Howard 发表于 2019-10-31 03:18:34 | 显示全部楼层
这个问题正好看过。回答会导致后面的朋友不愿再思索,但考虑到现在人气不行,本来也未必有人会思考,发于此
最佳策略是放弃前 0.37N 的西瓜,从下一个开始选,只要某瓜比前面见过的都大,就选它。如果一直没有,那就选最后一个。

其中0.37是1/e 也就是0.367879441。得到最大西瓜的概率也是1/e。

此算法可以最大化得到最大西瓜的概率。但得到的西瓜的平均大小期望值并不是最大的,因为并没有考虑第二大、第三大、第四大。。。。的西瓜。



如果要考虑挑到西瓜大小的平均排名最高,则要复杂得多。经过一番人神共愤的论证之后,用最佳方法,当N趋向于无穷时,挑到的西瓜的排名期望值是3.8695
notch 发表于 2019-10-31 08:32:20 | 显示全部楼层
Howard 发表于 2019-10-31 03:18
这个问题正好看过。回答会导致后面的朋友不愿再思索,但考虑到现在人气不行,本来也未必有人会思考,发于此 ...

老陈的问题正好之前也看过答案

很好奇howard题目中的人神共愤的最佳解法
twotu 发表于 2019-10-31 08:56:35 | 显示全部楼层
这个应该跟谈恋爱如何挑选到最佳伴侣的是同一道题吧
Howard 发表于 2019-11-5 02:05:12 | 显示全部楼层
notch 发表于 2019-10-30 18:32
老陈的问题正好之前也看过答案

很好奇howard题目中的人神共愤的最佳解法

这个结果是拒绝前√n (根号n)的西瓜,从下一个开始选比前面都大的

对于大多数n来说,√n < n/e,因此,要选择到期望值最大的西瓜,要比最大化选到最大西瓜的方法提前一些开始选。

论证过程说实在的我还看不懂,想卖弄也没办法
bedok 发表于 2019-11-5 10:55:40 来自手机 | 显示全部楼层
是否有假定西瓜的大小符合正态分布?
Howard 发表于 2019-11-5 22:13:04 | 显示全部楼层
bedok 发表于 2019-11-4 20:55
是否有假定西瓜的大小符合正态分布?

这个并没有。

1)首先,为了方便起见,论证此问题的过程,假定了是(0,1)上的均匀分布。
如果有100个西瓜,那瓜的大小分别是0.01, 0.02, 0.03... 1.00
N个西瓜则大小分别是1/N, 2/N, 3/N .... 1

2) 大小的分布并不影响计算过程和结果。
我们需要的只是排名。哪怕瓜在某一个区间大小特别集中,在其他的区间比较分散,也还是按照排名而已。从排名上看不出大小属性本身的,只是相对于其他瓜的大小。


bedok 发表于 2019-11-6 01:03:07 | 显示全部楼层
Howard 发表于 2019-11-5 22:13
这个并没有。

1)首先,为了方便起见,论证此问题的过程,假定了是(0,1)上的均匀分布。

如果假定了(0,1)的均匀分布, 那么如果来了一只0.99999998的瓜, 不管它是第几只瓜, 那当然就把它留下了.
如果假定是均匀分布, 且假定范围是(a,b), (a b 未知). 那么从前面n只瓜的采样, 也可以给出对a b的估计, 从而依据这个估计来求解
如果假定是正态分布, 均值和标准差未知. 那么从前面n只瓜的采样, 也可以给出对均值和标准差的估计, 从而依据这个估计来求解
由此可见分布的假定还是很重要的


Howard 发表于 2019-11-6 02:57:04 来自手机 | 显示全部楼层
此言甚是有理。我的均匀分布说法不正确,应该是未知的分布,随机的排序。


然而在生活中这种理想随机难以得到。比如说挑西瓜,我们都知道一个西瓜也就是五斤到20斤之间。看到一个40斤的,那不要再看了就选它。

再比如中文网络流行的“选对象”,人群中异性的平均分布大家基本上也有个估计,看到一个貌如林志玲,脾气又好,又会做家务的姑娘,那不用说也是top 1%,再遇到比她好的已经不太可能了

英文文献的原问题是选秘书。秘书的能力也有个生活常识即可判断的上下限。打字500每分钟,非常有条理,还随叫随到,还能提出建设性意见,这样的哪怕是第一个面试也得留下

要想找出一个纯未知分布的,还真不容易

还有个问题就是样本一大,基本就都是正态分布了,无论是何种性质的问题
bedok 发表于 2019-11-6 10:40:57 | 显示全部楼层
Howard 发表于 2019-11-6 02:57
此言甚是有理。我的均匀分布说法不正确,应该是未知的分布,随机的排序。

秘书的话, 其实可以让人回去等消息......
所以说选对象可能是最贴切的. 过去了的就真的只能过去了. 但是这个也说不定哎......旧情复燃也有可能.....

回到题目, 假定正态分布, 总共100只

举例说明: 当拿到第30只的时候, 均值是10斤, 标准差1斤. 计算得出大约12.3斤就可以收手了. 否则就拿第31只.重新计算均值和标准差.再来一遍.
火花的方法其实不错, 如果不能假定分布, 1/e大概是个不错的办法.



您需要登录后才可以回帖 登录 | 注册

本版积分规则

手机版|Archiver|智游城论坛

GMT+8, 2019-11-21 16:56 , Processed in 0.146407 second(s), 18 queries .

Powered by Discuz! X3.2

© 2001-2012 Comsenz Inc.

返回顶部