โปรแกรมนับภาคเรียนขั้นต่ำให้ครอบคลุมรายวิชาต่างๆ ใน ​​Python

สมมติว่าเรามีตัวเลข n แสดงว่ามี n หลักสูตรต่างๆ ที่มีป้ายกำกับตั้งแต่ 1 ถึง n เรายังมีอาร์เรย์ที่เรียกว่าความสัมพันธ์ โดยที่ความสัมพันธ์[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 ภาคการศึกษา

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ่าย :=ชุดใหม่

• g1 :=รายการที่มี n รายการว่าง

• g2 :=รายการขนาด n ใหม่และเติม 0

• w :=รายการขนาด n ใหม่และเติมด้วย 0

• ภาคการศึกษา :=0

• สำหรับแต่ละ x ในความสัมพันธ์ ทำ

  • แทรก x[0]-1 ที่ส่วนท้ายของ g1[x[1]-1]

  • ใส่ x[1]-1 ที่ส่วนท้ายของ g2[x[0]-1]

• weight :=รายการใหม่จากความยาวของรายการทั้งหมดใน g1

• สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ

  • สำหรับแต่ละ x ใน g1[i] ทำ

    • w[x] :=สูงสุดของ w[x] และน้ำหนัก[i]

• ในขณะที่ขนาดของถ่าย

  • รายวิชา :=รายการใหม่

  • สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ

    • ถ้า g1[i] ว่างและไม่ได้เข้าอยู่

      • แทรก (i, w[i]) เมื่อสิ้นสุดหลักสูตร

    • ถ้าขนาดคอร์ส>k แล้ว

      • หลักสูตร =จัดเรียงหลักสูตรตามพารามิเตอร์ที่สองในลำดับที่กลับกัน

      • รายวิชา :=รายวิชา k รายแรก

    • ภาคการศึกษา :=ภาคการศึกษา + 1

    • สำหรับแต่ละ x ในหลักสูตร ให้ทำ

      • สำหรับแต่ละ y ใน g2[x[0]] ให้ทำ

        • ลบ x[0] จาก g1[y]

      • g2[x[0]] :=รายการว่าง

      • แทรก x[0] ลงใน ถ่าย

• กลับภาคการศึกษา

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

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))

อินพุต

6, [(1,3),(2,5),(2,4),(5,6)], 2

ผลลัพธ์

3