[問題] 一題現實中的問題
看板Prob_Solve (計算數學 Problem Solving)作者GYLin (Lynx)時間5年前 (2019/03/09 08:59)推噓7(7推 0噓 8→)留言15則, 4人參與討論串1/1
由於是現實的問題 所以有沒有P的解我也不知道
還請各位見諒
問題如下:
有N個人(N<=60)參加面試
有M個部門(M=7)可以選
面試時間有T個(T=6)
每個人可以選1~3個部門面試
且每個人各有可以的時間(1~T之中任意選取)
======
想請問考慮所有部門的各時段(M*T個),
他們之中人數最大值, 最少可以是多少, 能讓所有人排到面試.
(各個人想面試的每個部門都要能面試到)
======
如果每個人只能選擇一個部門, 我有想到最大流的解法,
從原點流向每個人, 再從每個人流向M*T個時段,
調整各時段的出容量, 逐次加一, 當總流量=人數,
此出容量即為解.
但是當一個人可以面試多個部門, 我卡在一個人同時間不能出現在兩地,
不知道能不能依然用最大流解...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.226.98.184
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1552093196.A.728.html
※ 編輯: GYLin (36.226.98.184), 03/09/2019 09:02:17
推
03/09 12:06,
5年前
, 1F
03/09 12:06, 1F
是每個部門的每個時段 所以有T*M個 使當中的最大值最小
→
03/09 12:08,
5年前
, 2F
03/09 12:08, 2F
忘了還有這步可以用 感謝大大
不過還是有點好奇能不能用flow就是了
※ 編輯: GYLin (36.226.98.184), 03/09/2019 13:43:20
※ 編輯: GYLin (36.226.98.184), 03/09/2019 13:44:53
※ 編輯: GYLin (36.226.98.184), 03/09/2019 13:45:44
推
03/10 06:35,
5年前
, 3F
03/10 06:35, 3F
→
03/10 06:35,
5年前
, 4F
03/10 06:35, 4F
這樣可以避免同一個人時間衝到 但這樣每個node流入流出的量好像就不一定相等了?
※ 編輯: GYLin (36.226.98.184), 03/10/2019 22:38:16
推
03/11 06:23,
5年前
, 5F
03/11 06:23, 5F
對啊 我的意思是 用 C(T*M, 3) 個點
那這些點的流入量我猜就是每個人的選擇, 流出應該就是再流到T*M個node
分別代表T*M個時段分別被用到了幾次
但是這樣的話, 做了一個選擇, 流出量卻有可能需要三倍, 就無法使用flow了
勢必要有其他建圖方法, 但我還沒想到就是了
※ 編輯: GYLin (36.226.98.184), 03/11/2019 09:59:49
推
03/11 10:46,
5年前
, 6F
03/11 10:46, 6F
→
03/11 10:46,
5年前
, 7F
03/11 10:46, 7F
→
03/11 10:46,
5年前
, 8F
03/11 10:46, 8F
推
03/14 18:11,
5年前
, 9F
03/14 18:11, 9F
→
03/14 18:11,
5年前
, 10F
03/14 18:11, 10F
推
03/15 11:10,
5年前
, 11F
03/15 11:10, 11F
推
03/16 01:07,
5年前
, 12F
03/16 01:07, 12F
→
03/16 01:07,
5年前
, 13F
03/16 01:07, 13F
→
03/16 01:07,
5年前
, 14F
03/16 01:07, 14F
→
03/16 13:16,
5年前
, 15F
03/16 13:16, 15F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
