用 Python 编写一个程序，计算最少需要多少学期才能修完所有不同的课程

pythonserver side programmingprogramming更新于 2025/11/30 20:28:17

假设我们有一个数字 n，表示有 n 门不同的课程，编号从 1 到 n。我们还有一个名为 relationships 的数组，其中 relationships[i] 包含一对 (prevCourse_i, nextCourse_i)，表示课程 prevCourse_i 和课程 nextCourse_i 之间的先决条件关系:因此课程 prevCourse_i 必须在课程 nextCourse_i 之前修完。最后一个参数是 k。在一个学期中，我们最多可以修 k 门课程，只要我们在上一学期已经修完了我们正在修的课程的所有先决条件即可。我们必须找到修完所有课程所需的最少学期数。

因此，如果输入如下

那么输出将是 3，因为在第一个学期我们可以修完课程 1 和 2，现在我们有资格修完课程 3、4 和 5，因此如果我们在第二学期修完 5 门课程和 3 或 4 中的任何一门课程，那么我们就可以在下学期结束所有课程。所以我们总共需要 3 个学期

为了解决这个问题，我们将遵循以下步骤 −

taken := 一个新集合
g1 := 一个包含 n 个空列表的列表
g2 := 一个大小为 n 的新列表，并用 0 填充
w := 一个大小为 n 的新列表，并用 0 填充
semester := 0
对于关系中的每个 x，执行
- 在 g1[x[1]-1] 的末尾插入 x[0]-1
- 在 g2[x[0]-1] 的末尾插入 x[1]-1
weight := 一个由 g1 中所有项目的长度组成的新列表
对于i 在 0 到 n - 1 的范围内，执行
- 对于 g1[i] 中的每个 x，执行
  - w[x] := w[x] 和 weight[i] 的最大值
当所取的大小 < n，执行
- courses := 一个新列表
- 对于范围为 0 到 n - 1 的 i，执行
  - 如果 g1[i] 为空且 i 未被选出，则
    - 在 courses 末尾插入 (i, w[i])
  - 如果 courses 大小 > k，然后
    - courses = 根据第二个参数以相反顺序对课程进行排序
    - courses := 前 k 门课程的列表
  - semester := semester + 1
  - 对于 courses 中的每个 x，执行
    - 对于 g2[x[0]] 中的每个 y，执行
      - 从 g1[y] 中删除 x[0]
    - g2[x[0]] := 空列表
    - 将 x[0] 插入到 taken 中
返回 semester

示例

让我们看看下面的实现以便更好地理解

def solve(n, relations, k):
   taken = set()
   g1 = [[] for _ in range(n)]
   g2 = [[] for _ in range(n)]
   w = [0] * n
   semester = 0
   for x in relations:
      g1[x[1]-1].append(x[0]-1)
      g2[x[0]-1].append(x[1]-1)

   weight = list(map(len, g1))
   for i in range(n):
      for x in g1[i]:
         w[x] = max(w[x], weight[i])


   while len(taken) < n:
      courses = []
      for i in range(n):
         if (not g1[i]) and (i not in taken):
            courses.append([i,w[i]])
      if len(courses) > k:
         courses = sorted(courses, key = lambda x:x[1],reverse=True)
         courses = courses[:k]

      semester += 1

      for x in courses:
         for y in g2[x[0]]:
            g1[y].remove(x[0])
         g2[x[0]] = []
         taken.add(x[0])
   return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))