我應該用什麼來實現C++中的加權二分匹配算法？

我有一個項目，它要求我將課程分發給學生。所有學生都要求提供一些課程，但他們只能獲得一些課程（這可能是他們要求的，不到的或只是0 ），所有課程都有配額，我需要找到完美匹配（所有配額是否滿員，學生是否獲得了他們所允許的配額）是否存在 - 如果存在匹配的輸出。我應該用什麼來實現C++中的加權二分匹配算法？

我剛剛獲得輸入並將其存儲在對象中。項目中存在時間限制，我不知道從哪裏開始。對於此項目的任何建議或方法？

我想我應該實現二部匹配算法。我是新的C++，所以我需要實現節點類和邊類嗎？或者我應該使用鄰接列表？哪一個運行速度更快？

例如，學生要求3,4和5課程，但他可以上2節課，所以如果有完美匹配的可能性，算法應該給出2個選擇。

我認爲雙方面的問題是這樣的，但我認爲這很難實現。 http://i.stack.imgur.com/wtJ6o.jpg

1.student wants 3 ,4 system allows him to take 2 lessons 
2.student wants 1,2,3,4 system allows him to take 3 lessons 
3.student wants 1,2,3,4 system allows him to take 2 lessons 
4.student wants 1,3,5 system allows him to take 2 lessons 
5.student wants 2,5 system allows him to take 1 lessons 

1.lesson's quota = 2 
2.lesson's quota = 1 
3.lesson's quota = 2 
4.lesson's quota = 3 
5.lesson's quota = 2 

I just wrote this ,this might not be the best example. 
One possible solution is = 1 -> (3,4) 2->(1,2,4) 3->(3,4) 4->(1,5) 5->(5) 
Another is = 1 -> (3,4) 2->(1,2,4) 3->(1,4) 4->(3,5) 5->(5)

可能有更多的，我不知道。

（學生 - >教訓）

來源

2013-12-14 McOne

由於一個學生可以分配多個當然，我不認爲這個問題可以通過簡單的二分最大匹配算法來解決。

此問題是transportation problem的一種，其中課程爲sources，學生爲destinations。每門課程的配額爲capacity，demand爲每個學生的系統允許他的課程數量。

編輯：

您可以通過下面的修改制定的運輸問題：

分裂的教訓，使得每節課都有的1報價所以在你的榜樣情況下應當有10節課。分配成本如下：

Demand: 2 3 2 2 1 
     St1 St2 St3 St4 St5 
Less1.1 5 0 0 0 5 
Less1.2 5 1 1 1 5 // cost for second dummy lesson is slightly high to differentiate. 
Less2.1 5 0 0 5 0 
Less3.1 0 0 0 0 5 
Less3.2 1 1 1 1 5 
Less4.1 0 0 0 5 5 
Less4.2 1 1 1 5 5 
Less4.3 2 2 2 5 5 
Less5.1 5 5 5 0 0 
Less5.2 5 5 5 1 1

來源

2013-12-14 18:08:42

我並沒有完全理解您的意思是運輸問題和運輸成本。請您稍微擴展一下您的答案？我爲我的問題添加了一個方案。謝謝。 – McOne

但是沒有學生要上課，他/她沒有要求。所以沒有成本，因爲我認爲1。所有運輸的課程已經被要求 – McOne

@McOne如果學生沒有要求一個特定的課程，因爲我們已經使運輸成本高（1），所以該選項不應存在於最佳解決方案中。但是，我有可能誤解了這個問題。請提供一個工作示例來澄清問題。 –

我應該用什麼來實現C++中的加權二分匹配算法？

回答

相關問題