[問題] 一題現實中的問題

看板Prob_Solve (計算數學 Problem Solving)作者 (Lynx)時間5年前 (2019/03/09 08:59), 5年前編輯推噓7(708)
留言15則, 4人參與, 5年前最新討論串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
如果是實務上的問題 就建一個 integer programm 來解吧
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
因為每個人頂多只能面試三次 所以你只要用C(TM, 3) 個
03/10 06:35, 3F

03/10 06:35, 5年前 , 4F
node 就可以表示 constraint ?
03/10 06:35, 4F
這樣可以避免同一個人時間衝到 但這樣每個node流入流出的量好像就不一定相等了? ※ 編輯: GYLin (36.226.98.184), 03/10/2019 22:38:16

03/11 06:23, 5年前 , 5F
我不懂你的意思 流入和流出量不等還叫做 flow 嗎?
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
C(T*M, 3) 流入跟流出的 capacity 都是 1
03/11 10:46, 6F

03/11 10:46, 5年前 , 7F
T*M個node 流入 capacity 1 流出 capacity 3
03/11 10:46, 7F

03/11 10:46, 5年前 , 8F
這樣可行嗎?
03/11 10:46, 8F

03/14 18:11, 5年前 , 9F
flow 不會複製, 所以樓上那樣的 cap 3 永遠只會滿足至多 1
03/14 18:11, 9F

03/14 18:11, 5年前 , 10F
原 PO 現在的問題就是在這裡
03/14 18:11, 10F

03/15 11:10, 5年前 , 11F
喔喔 我想錯了
03/15 11:10, 11F

03/16 01:07, 5年前 , 12F
「每個人可以選1~3個部門面試」是說「每個人各自選好部門
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
謝謝LPH大大解釋,回樓上是前者
03/16 13:16, 15F
文章代碼(AID): #1SWn0CSe (Prob_Solve)
文章代碼(AID): #1SWn0CSe (Prob_Solve)