楼主:
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