PTT數位生活區 / C_and_CPP (C/C++)

[問題] 求問一題Maximum Flow?已刪文

看板C_and_CPP (C/C++)作者 (天馬)時間4年前 (2020/11/18 15:41), 編輯推噓9(9推 0噓 12→)
留言21則, 2人參與, 4年前最新討論串1/1
一個演算法的問題： 假設我要將x個學生"平均"分配給y個老師(x>y)，其中每個學生跟老師之間都有一個適合 度Kx,y，我希望分配後，合作度加總能夠最大，有人知道怎麼解嗎？ 我在想Maximum Flow或DP能不能解這個問題，如果沒有限制要平均分配(每個老師管到一 樣多的學生)，這題用Maximum Flow應該就可以解了，但加上這個條件的話呢？ 另外如果有人對分配的演算法很熟悉或有興趣，也歡迎討論，thanks! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.98 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1605685318.A.690.html
推
11/18 18:04, 4年前 , 1F
感覺要五維DP
11/18 18:04, 1F
推
11/18 18:10, 4年前 , 2F
更正 三維
11/18 18:10, 2F
推
11/18 18:17, 4年前 , 3F
好像一維就好了
11/18 18:17, 3F
→
11/18 18:18, 4年前 , 4F
先更正 二維
11/18 18:18, 4F
→
11/18 18:19, 4年前 , 5F
我回去再想 再吃飯
11/18 18:19, 5F
推
11/18 18:23, 4年前 , 6F
問你哦 如果窮舉所有平均人數的組合在用你說的maximum
11/18 18:23, 6F
→
11/18 18:23, 4年前 , 7F
flow 可以接受嗎？
11/18 18:23, 7F
→
11/18 18:23, 4年前 , 8F
至少不是從頭到尾無腦窮舉
11/18 18:23, 8F
推
11/18 18:40, 4年前 , 9F
先從一個學生一個老師思考試試看
11/18 18:40, 9F
推
11/18 18:44, 4年前 , 10F
一邊吃飯應酬一邊想太難了回去再想
11/18 18:44, 10F
→
11/18 18:45, 4年前 , 11F
反正不能用互斥窮舉就對了
11/18 18:45, 11F
→
11/18 18:45, 4年前 , 12F
？
11/18 18:45, 12F
→
11/18 18:58, 4年前 , 13F
窮舉 是列出所有可能的組合？那會很慢誒
11/18 18:58, 13F
推
11/18 18:59, 4年前 , 14F
bipartite graph???
11/18 18:59, 14F
→
11/18 19:01, 4年前 , 15F
目前有想到作法了，但可能也蠻慢的，DP有幾個細節還沒想
11/18 19:01, 15F
→
11/18 19:01, 4年前 , 16F
清楚
11/18 19:01, 16F
推
11/18 19:02, 4年前 , 17F
Maximum Bipartite Matching
11/18 19:02, 17F
→
11/18 19:02, 4年前 , 18F
GeeksforGeeks 這個應該蠻像的
11/18 19:02, 18F
→
11/18 19:03, 4年前 , 19F
我一開始也是想到那個
11/18 19:03, 19F
→
11/18 19:04, 4年前 , 20F
但應該不太一樣
11/18 19:04, 20F
推
11/18 19:05, 4年前 , 21F
等高手解答吧
11/18 19:05, 21F
‣ 更多 Emmanuel 的文章
文章代碼(AID): #1VjD16QG (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Emmanuel 的文章
文章代碼(AID): #1VjD16QG (C_and_CPP)