原始问题：波斯公主到了适婚年龄，要选驸马。候选男子100名，都是公主没有见过的。百人以随机顺序，从公主面前逐一经过。每当一位男子在公主面前经过时，公主要么选他为驸马，要么不选。如果选他，其余那些还没有登场的男子就都遣散回家，选驸马的活动也over了。如果不选，当下这名男子就离开，也就是pass掉此人，下一人登场。被pass掉的，公主不可以反悔再从选。规则是，公主必须在这百人中选出一人做驸马，也就是说，如果前99人公主都看不中的话，她必须选择第100名男子为驸马，不管他有多么丑陋。
那我们的任务就是，给公主设计选择方法，让她有最高概率选到百人中最英俊的男子为驸马。
问题转换为：假设有100个数字，无放回的抽取K个数字（每次一个）。寻找一种策略使得第K次抽取到最大数字的概率最大化。
假设：为了方便说明，假设最大数字只有一个。
粗糙的解法：随机选择一个K值,则第K次抽到最大数字的概率明显就是0.01。所以到目前为止，baseline=0.01. 我们需要寻找一种策略使得这个概率大于0.01.
原文：http://www.cnblogs.com/1zhk/p/4934273.html