作者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/cn.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