作者:
GtSoul (安蛇)
2016-04-04 20:54:18小弟最近研究的題目需要找類似的演算法
問題大概是這樣
一家餐廳的餐桌無限
每桌可以坐五個人
坐滿才開始上菜
客人可能跟朋友1～4人一起進來
朋友不分桌坐
要怎麼樣可以讓每個客人的等待時間最少
上網google了好久
但是沒有關鍵字實在找不到類似的
比較像的就是裝箱問題
請問版友們是否知道有更類似的演算法
或是這個問題已經有最佳解了
可以提供參考嗎
由於剩餘桌數的狀態有限 列幾個變數設期望值求解即可但有沒有更深的 insight 我就不知了 貪求應該不太行
作者:
FRAXIS (喔喔)
2016-04-05 10:35:00客人可能跟朋友1～4人一起進來 <- 所以每次進來的都是2 ~ 5 人一組？ 那這樣只有 2 + 3 才能湊一桌不是嗎？
他意思應該是進來可能人數就是 1~4 人不過我第一推的狀態有限是錯的 抱歉
作者:
GtSoul (安蛇)
2016-04-05 14:39:00抱歉，文意上造成誤會，是自己+朋友，可能為1～4人一起進來
作者:
FRAXIS (喔喔)
2016-04-05 18:33:00其實題意還是很不清啊 輸入到底是什麼？ 時間點 + 人數？還是是一個隨機分布？ 還是要考慮 streaming/online algo?等待時間最少是指平均等待時間? 最長等待時間？ 還是?
作者:
suhorng ( )
2016-04-08 19:38:00通靈下: 輸入是一個 sequence {x_i}_1^∞, x_i\in 1..4Σ_{k\in S} x_k = 5 時進餐; 這一桌等待的時間姑且當做max S - min S好吧其實也不對 完全沒講等待時間怎麼定義XD
他說每人，所以就 expectation 取兩次阿XD