[問題] 並桌問題

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