Chương trình tìm cách học tập hiệu quả nhất với deadline, credit, duration trong Python

Cho 3 mảng cùng độ dài: deadlines, credits, durations cho các bài tập. Làm tuần tự, phải xong trước deadline (ngày deadline vẫn tính kịp). Bắt đầu ngày 0. Tối ưu tổng credit.

Ví dụ: deadlines=[7,5,10], credits=[8,7,10], durations=[5,4,10] → 10.

Giải thuật (DP sắp xếp theo deadline)

1. Gộp và sắp xếp các bài theo deadline tăng dần.
2. DP dp(i, day): credit max từ bài i trở đi, hiện tại ở ngày day.
3. Chuyển trạng thái: không làm bài i hoặc làm (nếu day + duration - 1 <= deadline).

Lưu ý: Cần memoization. Độ phức tạp O(n * max_deadline).

Ví dụ minh họa

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=0, day=0):
            if i >= len(jobs):
                return 0
            ans = dp(i + 1, day)
            deadline, duration, credit = jobs[i]
            if day + duration - 1 <= deadline:
                ans = max(ans, dp(i + 1, day + duration) + credit)
            return ans
        
        return dp()

ob = Solution()
deadlines = [7, 5, 10]
credits = [8, 7, 10]
durations = [5, 4, 10]
print(ob.solve(deadlines, credits, durations))  # Output: 10

Đầu vào / Đầu ra

Input: [7,5,10], [8,7,10], [5,4,10]

Output: 10