作者GYLin (Lynx)
看板Prob_Solve
標題[問題] 一題現實中的問題
時間Sat Mar 9 08:59:53 2019
由於是現實的問題 所以有沒有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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1552093196.A.728.html
※ 編輯: GYLin (36.226.98.184), 03/09/2019 09:02:17
1F：推 FRAXIS: 最大人數最小值 <- 你是說部門人數嗎？ 03/09 12:06
是每個部門的每個時段 所以有T*M個 使當中的最大值最小
2F：→ FRAXIS: 如果是實務上的問題 就建一個 integer programm 來解吧 03/09 12:08
忘了還有這步可以用 感謝大大
不過還是有點好奇能不能用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
3F：推 FRAXIS: 因為每個人頂多只能面試三次 所以你只要用C(TM, 3) 個 03/10 06:35
4F：→ FRAXIS: node 就可以表示 constraint ？ 03/10 06:35
這樣可以避免同一個人時間衝到 但這樣每個node流入流出的量好像就不一定相等了?
※ 編輯: GYLin (36.226.98.184), 03/10/2019 22:38:16
5F：推 FRAXIS: 我不懂你的意思 流入和流出量不等還叫做 flow 嗎？ 03/11 06:23
對啊 我的意思是 用 C(T*M, 3) 個點
那這些點的流入量我猜就是每個人的選擇, 流出應該就是再流到T*M個node
分別代表T*M個時段分別被用到了幾次
但是這樣的話, 做了一個選擇, 流出量卻有可能需要三倍, 就無法使用flow了
勢必要有其他建圖方法, 但我還沒想到就是了
※ 編輯: GYLin (36.226.98.184), 03/11/2019 09:59:49
6F：推 FRAXIS: C(T*M, 3) 流入跟流出的 capacity 都是 1 03/11 10:46
7F：→ FRAXIS: T*M個node 流入 capacity 1 流出 capacity 3 03/11 10:46
8F：→ FRAXIS: 這樣可行嗎？ 03/11 10:46
9F：推 LPH66: flow 不會複製, 所以樓上那樣的 cap 3 永遠只會滿足至多 1 03/14 18:11
10F：→ LPH66: 原 PO 現在的問題就是在這裡 03/14 18:11
11F：推 FRAXIS: 喔喔 我想錯了 03/15 11:10
12F：推 lancerd: 「每個人可以選1~3個部門面試」是說「每個人各自選好部門 03/16 01:07
13F：→ lancerd: 了，部門數量最多是三個」，還是說你的答案要讓「每個人 03/16 01:07
14F：→ lancerd: 隨便選三個部門」的所有情況都滿足？ 03/16 01:07
15F：→ GYLin: 謝謝LPH大大解釋，回樓上是前者 03/16 13:16