โปรแกรมหาวิธีเรียนรู้ที่มีประสิทธิภาพสูงสุดใน Python

มีงานบ้าน 3 ลิสต์: deadlines, credits, durations (ความยาวเท่ากัน) งาน i: ต้องเสร็จก่อน deadlines[i] ได้ credits[i] ใช้เวลา durations[i] วัน ทำทีละงาน เริ่มวัน 0 หา credit สูงสุด

ตัวอย่าง

deadlines = [7, 5, 10], credits = [8, 7, 10], durations = [5, 4, 10]

Output: 10

เลือกงานที่ 3 (duration 10, deadline 10, credit 10) หรืองาน 1+2 (5+4=9 ≤ deadline 5,7)

แนวทางแก้ปัญหา

DP + Sort by Deadline (Weighted Interval Scheduling):

1. รวมเป็น jobs = (deadline, duration, credit) เรียงตาม deadline
2. DP: dp(i, day) = max credit จากงาน i เป็นต้นไป เริ่มวันที่ day
3. Transition: ข้ามงาน i, หรือ ทำงาน i (ถ้า day + duration - 1 ≤ deadline)

การใช้งาน (Python - Memoized)

from functools import lru_cache

class Solution:
    def solve(self, deadlines, credits, durations):
        jobs = sorted(zip(deadlines, durations, credits))
        
        @lru_cache(None)
        def dp(i, day):
            if i >= len(jobs):
                return 0
            
            # Option 1: skip
            ans = dp(i + 1, day)
            
            # Option 2: take
            deadline, duration, credit = jobs[i]
            if day + duration - 1 <= deadline:
                ans = max(ans, dp(i + 1, day + duration) + credit)
            
            return ans
        
        return dp(0, 0)

# ทดสอบ
ob = Solution()
print(ob.solve([7, 5, 10], [8, 7, 10], [5, 4, 10]))  # Output: 10

ความซับซ้อน

• Time Complexity: O(N × MaxDay) - pseudo-polynomial
• Space Complexity: O(N × MaxDay)

สำหรับค่า deadline ใหญ่ ควรใช้ DP แบบ compress state หรือ greedy + heap (ถ้า duration=1)