这个问题蛮好玩的。 假设平均等待时间以客人组为单位，例如第一组客人来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/cn.aspx?n=bbs/Prob_Solve/M.1463134924.A.0E4.html