-1

问题：给定一组必修课和选修课，每门课程仅在特定时间段（有 7 个时间段）提供，生成所有可能的时间表。

例子：

对于必修课：

  • MAT101 - 1、2、5
  • HIS102 - 2、4、6
  • ENG105 - 3、6、7

和选修课：

  • LIT103 - 3、4、6
  • CHE101 - 7、1、2
  • 生物 101 - 5、4、7
  • MAT201 - 6、5、1
  • ANT201 - 1

（并非每门选修课都必须包含在时间表中）

可能的解决方案之一是：

  1. MAT101 [必修]
  2. HIS102 [强制性]
  3. LIT103
  4. 生物101
  5. MAT201
  6. ENG105 [必修]
  7. 车101

用 PHP 编写它的最有效方法是什么？

我目前正在尝试开发一个蛮力解决方案，但这是一项非常乏味的任务，我正在寻找更有效的方法来做到这一点。我发现这是一个 NP 完全问题，并搜索了有助于解决此类问题的 PHP 类，但恐怕目前没有这样的类可用。

4

2 回答 2

0

首先，我同意 Bryan 的观点，您首先需要对问题有充分的了解，然后至于算法，互联网上有它们的音调。

您说并非所有可选课程都必须包括在内，这意味着这种模式是唯一被接受的模式：

obc xxxxxx

其中 obc 是必修课，x 是必修课或可选课。顺序当然不重要。

如果你有 N 门必修课和 M 门选修课（显然 N+M>7 或 N+M=7），那么你只能有 N 种上述类型的接受模式。

然后你必须找到这种所有不同的时间表：

XXXXXX（6门课程）

这里顺序无关紧要，不允许重复，因此您需要（N + M）中的6个组合，这将使得：

(N+M)!/[6!(N+M-6)!] = K different such timetables.

那么 7 门课程的所有不同时间表将是：

K+K+...+K (N次) = N*K

（仔细检查是否正确，今天真的很累，否则会提示一些代码）。

我希望这能有所帮助。

于 2011-11-06T21:42:19.970 回答
0

问题：

问题：给定一组必修课和选修课，每门课程都只在特定的时间段（有 7 个时间段）可用，生成所有可能的时间表。

这里的关键是生成所有可能的时间表。这样做很简单，但是以任何方式切片都需要指数级的时间，因为您实际上是在列出整个搜索空间（可能性）。

这将是递归的并采用对的列表，对的第一个是时隙，对的第二个元素是可以填充时隙的可能类的列表。数据结构如下所示：

对于必修课：

  • 1 - MAT101、CHE101、MAT201、ANT201
  • 2 - MAT101、HIS102、CHE101
  • 3 - ENG105，LIT103

等需要加粗的课程。它还需要一个已经被该方法的先前递归调用选择的课程列表。

该功能将

  • 检查可能性列表（如上所述）是否与已选择的课程列表一起包含所有必修课程。如果没有，请返回。
  • 选择第一个可用的时间段（称为 myPick），然后
  • 对于将填补该时间段的每个可能的类（称为 currentClass），
    • 如果此方法在其第一个参数中仅给出 1 个时隙，
      • 打印已经选择的类列表（作为参数给出）。
      • 打印 "$currentClass $myPick\n",
      • 打印一个额外的换行符来分隔列表。返回。
    • 否则递归调用该方法，在其中向它提供您尚未选择的时隙列表（作为参数给出的时隙列表减去您刚刚在步骤 2 中选择的时隙列表），除了每个可能性列表时隙已从其中删除了您打印的课程。递归调用的第二个参数应该是给这个调用实例的已经选择的类的列表，并<currentClass,myPick>在列表中添加了 ()。

这应该让你开始。

于 2011-12-02T16:18:37.237 回答