选西瓜

有N(很多)个西瓜，让你选一个。规则是，拿来一个西瓜，你可以选中，此时选西瓜结束，如果你拒绝这个西瓜，再拿一个西瓜让你选，重复第一个的办法。拿来一个西瓜让你选时你无法知道后面西瓜的大小，可以知道还有多少个西瓜。显然随便选一个，选中最大的西瓜的概率为1/N，采用什么策略可以提高选中最大西瓜的概率？

这个问题正好看过。回答会导致后面的朋友不愿再思索，但考虑到现在人气不行，本来也未必有人会思考，发于此
最佳策略是放弃前 0.37N 的西瓜，从下一个开始选，只要某瓜比前面见过的都大，就选它。如果一直没有，那就选最后一个。

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

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



如果要考虑挑到西瓜大小的平均排名最高，则要复杂得多。经过一番人神共愤的论证之后，用最佳方法，当N趋向于无穷时，挑到的西瓜的排名期望值是3.8695

Howard 发表于 2019-10-31 03:18
这个问题正好看过。回答会导致后面的朋友不愿再思索，但考虑到现在人气不行，本来也未必有人会思考，发于此 ...

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

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

这个应该跟谈恋爱如何挑选到最佳伴侣的是同一道题吧

notch 发表于 2019-10-30 18:32
老陈的问题正好之前也看过答案

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

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

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

论证过程说实在的我还看不懂，想卖弄也没办法

是否有假定西瓜的大小符合正态分布？

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

Howard 发表于 2019-11-5 22:13
这个并没有。

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

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

此言甚是有理。我的均匀分布说法不正确，应该是未知的分布，随机的排序。


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

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

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

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

还有个问题就是样本一大，基本就都是正态分布了，无论是何种性质的问题

Howard 发表于 2019-11-6 02:57
此言甚是有理。我的均匀分布说法不正确，应该是未知的分布，随机的排序。

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

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

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