作者GtSoul (安蛇)
看板Prob_Solve
標題[問題] 並桌問題
時間Mon Apr 4 20:54:18 2016
小弟最近研究的題目需要找類似的演算法
問題大概是這樣
一家餐廳的餐桌無限
每桌可以坐五個人
坐滿才開始上菜
客人可能跟朋友1～4人一起進來
朋友不分桌坐
要怎麼樣可以讓每個客人的等待時間最少
上網google了好久
但是沒有關鍵字實在找不到類似的
比較像的就是裝箱問題
請問版友們是否知道有更類似的演算法
或是這個問題已經有最佳解了
可以提供參考嗎
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.98.29
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1459774460.A.F4C.html
1F：推 arthurduh1: 由於剩餘桌數的狀態有限 列幾個變數設期望值求解即可 04/04 20:57
2F：推 arthurduh1: 但有沒有更深的 insight 我就不知了 貪求應該不太行 04/04 21:03
3F：推 FRAXIS: 客人可能跟朋友1～4人一起進來 <- 所以每次進來的都是 04/05 10:35
4F：→ FRAXIS: 2 ~ 5 人一組？ 那這樣只有 2 + 3 才能湊一桌不是嗎？ 04/05 10:35
5F：推 arthurduh1: 他意思應該是進來可能人數就是 1~4 人 04/05 13:24
6F：→ arthurduh1: 不過我第一推的狀態有限是錯的 抱歉 04/05 13:24
7F：→ GtSoul: 抱歉，文意上造成誤會，是自己+朋友，可能為1～4人一起進 04/05 14:39
8F：→ GtSoul: 來 04/05 14:39
9F：推 FRAXIS: 其實題意還是很不清啊 輸入到底是什麼？ 時間點 + 人數？ 04/05 18:33
10F：→ FRAXIS: 還是是一個隨機分布？ 還是要考慮 streaming/online algo? 04/05 18:34
11F：→ FRAXIS: 等待時間最少是指平均等待時間? 最長等待時間？ 還是? 04/05 18:35
12F：推 suhorng: 通靈下: 輸入是一個 sequence {x_i}_1^∞, x_i\in 1..4 04/08 19:38
13F：→ suhorng: Σ_{k\in S} x_k = 5 時進餐; 這一桌等待的時間姑且當做 04/08 19:40
14F：→ suhorng: max S - min S 04/08 19:40
15F：→ suhorng: 好吧其實也不對 完全沒講等待時間怎麼定義XD 04/08 19:41
16F：推 arthurduh1: 他說每人，所以就 expectation 取兩次阿XD 04/08 20:05
17F：推 xsssxxzz: 把model 先寫出來吧...動態規劃寫看看 05/11 09:04