โปรแกรมนับภาคเรียนขั้นต่ำเพื่อเรียนครบทุกวิชาใน Python

ปัญหา

มี n วิชา (1 ถึง n) และ relations เป็นคู่ (prevCourse, nextCourse) แสดงว่า prev ต้องเรียนก่อน next แต่ละภาคเรียนเรียนได้สูงสุด k วิชา ต้องเรียนครบทุกวิชาในภาคเรียนน้อยที่สุด

ตัวอย่าง

n=6, relations=[(1,3),(2,5),(2,4),(5,6)], k=2 → ผลลัพธ์ 3 (ภาคเรียนที่ 1: วิชา 1,2; ภาคเรียนที่ 2: วิชา 5 และ 3 หรือ 4; ภาคเรียนที่ 3: วิชาที่เหลือ)

ขั้นตอนการแก้ปัญหา

1. taken := set(), g1 := [ [] for _ in range(n) ] (prerequisites), g2 := [ [] for _ in range(n) ] (dependents)
2. w := [0]*n (น้ำหนัก), semester := 0
3. สร้างกราฟจาก relations
4. weight := [len(g1[i]) for i in range(n)]
5. คำนวณ w: สำหรับแต่ละ i, สำหรับแต่ละ x ใน g1[i]: w[x] = max(w[x], weight[i])
6. بينما len(taken) < n:
   • courses := []
   • รวบรวมวิชาที่ g1[i] ว่าง และ i not in taken ใส่ courses พร้อม w[i]
   • ถ้า len(courses) > k: เรียง courses ตามน้ำหนักมากไปน้อย เลือก k อันแรก
   • semester += 1
   • สำหรับแต่ละ x ใน courses:
     • ลบ x[0] ออกจาก g1[y] สำหรับทุก y ใน g2[x[0]]
     • g2[x[0]] := []
     • เพิ่ม x[0] เข้า taken
7. คืน semester

การนำไปใช้งาน (Python)

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