這個問題蠻好玩的。 假設平均等待時間以客人組為單位，例如第一組客人來3個，第二組客人來2個， 第一組客人等了一組客人，等待組數為 1。第二組客人不用等，等待時間為 0。 這種情況下平均等待時間為 (1 + 0) / 2 = 0.5 組客人。 我們可以知道極限就是 0.5 ，因為你最快就是兩組人併一桌。 如果用一種只容許兩組客人併一桌的演算法呢？ 客人來就塞著，等到另一組加起來等於 5 的客人來了直接併桌。 可以算出設現在來的這組客人為 n 個人，來另一組剛好併桌的機率為 1/4 * 0.5 (平均等待時間為 0.5 組客人) + 3/4 * 1/4 * 1 (一組沒中一組中，沒中的不論，平均等待時間為 2 + 0 = 1) + 3/4 ^ 2 (平方) * 1/4 * 1.5 （二組沒中，第三組中） + 3/4 ^ 3 (立方) * 1/4 * 2　（三組沒中，第四組中） + ... 這個數例我不會算，用 java 跑到 1000 結果收斂在 2。 亦即不管現在來幾個人，等到剛好可以併桌需要平均等 2 組， 這個值很有趣！ 理論上的最佳演算法會讓平均等待客人組數落在等 0.5 組 ~ 2 組之間。 但實際上不是這樣的，假設你容許塞好塞滿好了。 現在併著等開桌的人不管是多少人(小於5人），等到下一組剛好可以併桌的 平均等待組數是 2 。 但併好桌的人有分先後，所以其實平均待待組數要比 2 大。 所以 2 可能也是演算法的最佳解， 我時間不夠趕著下班接小孩，只能先分享到這個地方。請大家多多指教。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.51.201.213 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1463134924.A.0E4.html