0

我有一个项目，它要求我将课程分发给学生。所有学生都要求一些课程，但他们只能获得一些课程（可能是他们要求的，少于或只有 0），所有的课程都有配额，我需要找到完美匹配（所有配额都已满，学生得到了他们被允许的）是否存在——如果存在匹配的输出。

到目前为止，我只是获取输入并将其存储在对象中。项目有时间限制，我不知道从哪里开始。对这个项目有什么建议或方法吗？

我想我应该实现二分匹配算法。我是 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)

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

（学生 -> 课程）

4

1 回答 1

0

由于一个学生可以分配多门课程，我认为这个问题不能通过简单的最大二分匹配算法来解决。

这个问题是一种交通问题，课程是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-14T18:08:42.480 回答