选中最重物体的策略

LLJ_LLJ

有n 个外形完全一样的物体，重量两两不等，不用秤称不能判断谁轻谁重。 现在你可以随便挑选一个，称它的重量（每次只能选一个），然后决定是否选中它，也可以放弃，然后称下一个。 只要你决定选中它，挑选过程就结束。而你一旦放弃它，以后不能再选它。 你的最终目的是选中它们最重的一个。 现在请设计一个选物体的策略，使得选中最重物体的概率最高。

wayne

似乎可以用上排序算法： http://bbs.emath.ac.cn/thread-1266-1-1.html

mathe

这个是老题目了,印象中通常这个题目是以招聘或者找对象的形式出现的

kon3155

见最佳约会策略 http://zhiqiang.org/blog/posts/t ... ating-strategy.html

wayne

长见识了，1/e竟然有如此特殊的意义

gxqcn

难怪有人会把在学校谈恋爱称作“打草稿” 不过人与人本身是无法比较的，就好比两个复数不可比较大小一样。

LLJ_LLJ

由于k是整数，k不可能取到 n/e 的值，那么k 可取 n/e 的两边的整数值， 用int(n/e) 和 int(n/e) +1 来表示 这两个整数值。 int（）是取整函数。 那么 概率最高的策略 所取的k 是不是 一定是上述整数二者之一呢? 如何能证明它。 用P（k） 表示策略（ 放弃前面k个物体，从k+1次开始，若比前面的都重，就选中该物体）选中最重物体的概率。 那么求证：P（k）的最大值在 int(n/e) 或 int(n/e) +1 时取得。 e是自然对数。

mathe

我们记P(k)为放弃前k个,然后从k+1个开始,第一个比前k个都重的就选中,那么选中最重物体的概率. 由于最重物体分别是第一个,第二个,...,第n个的概率都相等,都是$1/n$, 而如果最重物体在第h个($h>=k+1$),那么这种方法会选中最重物体的充分必要条件是前h-1个物体中,最重的物体出现在前k个中,所以这个概率为$k/{h-1}$,于是我们可以得出 $P(k)=\sum_{h=k+1}^n k/{h-1}$

mathe

于是$P(k+1)-P(k)=\sum_{h=k+1}^n1/{h-1}-1=\sum_{h=k}^{n-1}1/h-1$ 于是我们可以知道,最大的P(k)满足$k=min{k| \sum_{h=k}^{n-1}1/h<1}$ 谁来用计算机检验一下看看,这个数据同$n/e$近似程度有多好.而可以非常容易知道的是n充分大时,这个数同n的比值趋向1/e.

LLJ_LLJ

概率通项公式还要乘以1/n才对 。 还有：P（k）的最大值在 int(n/e) 或 int(n/e) +1 时取得。 对于n 不大时也是成立的，与 n 是否足够大无关。