[問題] 求問一題Maximum Flow?

作者: Emmanuel (天馬)   2020-11-18 15:38:40
一個演算法的問題:
假設我要將x個學生"平均"分配給y個老師(x>y),其中每個學生跟老師之間都有一個適合
度Kx,y,我希望分配後,合作度加總能夠最大,有人知道怎麼解嗎?
我在想Maximum Flow或DP能不能解這個問題,如果沒有限制要平均分配(每個老師管到一
樣多的學生),這題用Maximum Flow應該就可以解了,但加上這個條件的話呢?
另外如果有人對分配的演算法很熟悉或有興趣,也歡迎討論,thanks!
作者: s0914714 (YA)   2020-11-18 16:05:00
直覺想到是背包問題
作者: ucrxzero (RX-0)   2020-11-18 22:57:00
有想到嗎?
作者: oToToT (屁孩)   2020-11-19 15:31:00
minimum cost flow problem? btw 其實這感覺可以去Prob_Solve板問
作者: ucrxzero (RX-0)   2020-11-19 16:00:00
樓主一直說他想到了也不提示

Links booklink

Contact Us: admin [ a t ] ucptt.com