問(wèn)題: 有n個(gè)數(shù)字,要求你在線(xiàn)的選擇其中一個(gè)最大的,在選擇第i個(gè)之前,你知道前i-1次的數(shù)字是什么,但是無(wú)法知道你將要選擇的數(shù)字和以后待選的數(shù)字的大小。
一個(gè)很自然的策略是選定一個(gè)K,先看一下前k個(gè)的大小,不做任何選擇,然后繼續(xù)看,知道遇到一個(gè)比這之前的k個(gè)人還好。可以證明k= n/e 的時(shí)候,能夠獲得最好的選擇,能夠選擇到最大的那個(gè)。證明其實(shí)是比較簡(jiǎn)單的。假設(shè)在我們的某次選擇中,選擇第i個(gè)是最優(yōu)選擇,那么很顯然第i個(gè)必須是這n個(gè)數(shù)中最大的,那么此時(shí)的概率是1/n,第二個(gè)要求是前k個(gè)數(shù)中存在這i個(gè)數(shù)中次大的數(shù),否則是不會(huì)選擇第i個(gè)的。此時(shí)的概率是k/i-1,所以把第k個(gè)到第n個(gè)累加起來(lái)就OK了,然后取得次數(shù)的最大數(shù),可以計(jì)算獲得k=n/e。
很顯然這個(gè)問(wèn)題是一個(gè)在線(xiàn)算法的問(wèn)題,無(wú)法預(yù)知之后的情況,邊輸入邊進(jìn)行處理。而離線(xiàn)算法是要求當(dāng)輸入完成之后,然后進(jìn)行輸出。 在線(xiàn)算法的目的就是能夠達(dá)到離線(xiàn)算法的一樣好的效果。
題目來(lái)源:
http://zhiqiang.org/blog/science/tcs-classroom-notes-the-best-dating-strategy.html
http://www.cnblogs.com/fll/archive/2008/06/01/1211569.html