0

问题是：

考虑到在一周的一天中，学生至少有这些课程中的一门，最多 3 节课，没有不管它们如何混合”

M: [数学,数学,数学]
T: [pc progr,pc progr]
W: [pc progr]
T: [物理]
F: [物理]

我有一个想法在 Python 中创建一个包含 15 个元素的列表，该列表将包含一周 15/5 = 3 的所有课程（学生可以拥有的最大课程），因此对于上面的示例，列表看起来像[m,m,m,cs,cs,0,cs,0,0,p,0,0,p,0,0]但我没有t 真的知道如何使用回溯生成所有列表。你能给我一些想法吗？

4

1 回答 1

1

首先尝试解决一个更简单的问题。尝试输出所有可能的混合具有两个约束的类：

  1. 一天不能出现超过一次的课程

  2. 一天的课程顺序无关紧要

像往常一样，回溯问题最容易用递归来解决。执行以下操作：以任何顺序 cs,cs,cs,m,m,m,p,p 获取类的序列，并在递归的每一步将下一个类分配给“可能”的一天。如果到目前为止分配的班级少于 3 个，并且还没有相同类型的班级，那么一天是可能的。

为了避免重复的可能性，增加了一个要求 - 如果在递归的当前步骤中，我们需要将 A 类分配给某天并且 A 类已经添加到某些天，那么只尝试将 A 分配给几天后在一周内，然后是它被分配到的最后一个。由于这听起来有点令人困惑，让我举个例子：

假设我们有当前状态：

M: m, cs
T: 0
W: cs
T: p
F: p

下一步我们必须添加一个cs类。如上所述，我们只会在 W 之后的几天尝试，即星期四和星期五。这需要一些考虑，但您应该能够弄清楚，如果我们不添加此限制，则可能会发现不止一次。

递归结束有两种情况：

  • 如果所有的类都被分配到某一天，我们找到了一个可能的分配，我们输出它

  • 如果在下一步我们需要将 A 类分配给某一天，但 A 已经被分配到一周中的某一天，比如 X 并且 X 之后的所有天都已经分配了 3 个类，那么我们找不到可能的一天对于 A ，因此在此分支中找不到可能的解决方案。

现在解决了这个更容易的问题，尝试删除我添加的两个附加约束。首先修改解决方案，使一个类可能一天出现一次以上（尽管在这种情况下问题似乎更简单，需要额外的工作来避免多次计算某些可能性）。在此之后删除最后剩余的约束 - 使一天中的课程顺序很重要。有一种简单的方法，但我不确定在您陈述问题时是否允许 - 在找到解决方案后，在其中的所有日子里进行所有排列以生成所有可能的安排。

我真的希望这个答案有所帮助。我可以写下我上面提到的所有问题的解决方案，但我更愿意尝试给你一些提示，告诉你如何自己解决这些问题，这样你就可以自己动手了。

于 2012-01-15T14:15:53.943 回答