用 PHP 编写课程时间表系统最有效的方法是什么？
问题： 给定一组必修课和选修课，每个课程仅在特定时间段（有 7 个时间段）提供，生成所有可能的时间表。
示例：
必修课程：
- MAT101 - 1, 2, 5
- HIS102 - 2, 4, 6
- ENG105 - 3, 6, 7
选修课程：
- LIT103 - 3, 4, 6
- CHE101 - 7, 1, 2
- BIO101 - 5, 4 , 7
- MAT201 - 6, 5, 1
- ANT201 - 1
（并非每门选修课程都必须包含在时间表中）
可能的解决方案之一是：
- MAT101 [必修]
- HIS102 [必修]
- LIT103
- BIO101
- MAT201
- ENG105 [必修]
- CHE101
用 PHP 编写最有效的方法是什么？
我目前正在尝试开发一个强力解决方案，但这是一项非常乏味的任务，我正在寻找更有效的方法来完成它。我发现这是一个 NP 完全问题，并搜索了有助于解决此类问题的 PHP 类，但恐怕目前没有这样的类。
Problem:
Given a set of obligatory and optional courses each being available only in certain time slots (there are 7 time slots) generate all possible timetables.
Example:
For obligatory courses:
- MAT101 - 1, 2, 5
- HIS102 - 2, 4, 6
- ENG105 - 3, 6, 7
And optional courses:
- LIT103 - 3, 4, 6
- CHE101 - 7, 1, 2
- BIO101 - 5, 4, 7
- MAT201 - 6, 5, 1
- ANT201 - 1
(not every optional course must be included in a timetable)
One of the possible solutions would be:
- MAT101 [obligatory]
- HIS102 [obligatory]
- LIT103
- BIO101
- MAT201
- ENG105 [obligatory]
- CHE101
What's the most efficient way to write it in PHP?
I'm currently trying to develop a brute-force solution, but it's a very tedious task and I'm looking for more efficient ways to do it. I figured out it's a NP-complete problem and searched for PHP classes helpful in solving such a problems, but I'm afraid there is no such a class available at the moment.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
首先，我同意布莱恩的观点，你首先需要对问题有充分的了解，然后至于算法，互联网上有他们的说法。
您说并非每门选修课程都必须包括在内，这意味着这种模式是唯一接受的：
其中 obc 是必修课程，x 是必修或可选课程。当然顺序并不重要。
如果你有 N 门必修课和 M 门选修课（显然 N+M>7 或 N+M=7），那么你只能有 N 种接受的上述类型的模式。
然后你必须找到这种类型的所有不同时间表：
XXXXXX（6门课程）
这里顺序无关紧要并且不允许重复，所以你需要（N+M）中的6个组合，这将使得：
那么7门课程的所有不同时间表将是：
（仔细检查是否正确，今天真的很累，否则会建议一些代码）。
我希望这能有所帮助。
First of all I agree with Bryan you first need to have a full understanding of the problem, then as for the algorithm the internet has tones of them.
You said that not every optional course must be included, this means that this pattern is the only one accepted:
where obc is an obligatory lesson and x is obligatory or optinal. Order does not matter of course.
If you have N obligatory and M optional courses (obviosuly N+M>7 or N+M=7) then you can only have N accepted patterns of the above kind.
Then you have to find all different timetables of this kind:
X X X X X X (6 courses)
here the order does not matter and repetiotion is not allowed, so you need combinations of 6 out of (N+M) which will make:
Then all different timetables of 7 courses would be:
(Check carefully if this is correct, really tired today, otherwise would suggest some code).
I hope this can be of some help.
问题：
这里的关键是生成所有可能时间表。这样做很简单，但无论以何种方式切片都会花费指数时间，因为您实质上列出了整个搜索空间（可能性）。
这将是递归的并采用一个对列表，该对中的第一个元素是时隙，该对中的第二个元素是可以填充时隙的可能类的列表。数据结构如下所示：
对于必修课程：
等，其中粗体课程为必修课程。
它还需要一个已经由该方法的先前递归调用选择的课程列表。
该函数将
这应该可以帮助您开始。
The problem:
The key here is generate all possible timetables. doing this is simple, but takes exponential time any way you slice it, because you are essentially listing the entire search space (possibilities).
The would be recursive and take a list of pairs, the first of the pair being a time slot and the second element of the pair being a list of possible classes that could populate time slot. The data structure would look like this:
For obligatory courses:
etc. where bolded courses are required.
It would also take a list of courses which have already been picked by previous recursive calls of the method.
The function would
<currentClass,myPick>) added to the list.This should get you started.