Chương trình tìm tín dụng tối đa mà chúng tôi có thể nhận được bằng cách hoàn thành một số bài tập trong python

Giả sử chúng ta có hai danh sách có cùng kích thước, đây là thời hạn và tín chỉ và chúng đại diện cho các bài tập của khóa học. Ở đây deadline [i] hiển thị ngày hạn chót cho nhiệm vụ i và tín chỉ [i] thể hiện số tín chỉ chúng ta nhận được cho nhiệm vụ i. Chúng tôi có một ngày để hoàn thành bài tập và có thể hoàn thành trước hoặc vào ngày hạn chót. Chúng ta không thể thực hiện nhiều nhiệm vụ cùng một lúc. Chúng tôi phải tìm được tín dụng tối đa mà chúng tôi có thể đạt được bằng cách hoàn thành một số bài tập con.

Vì vậy, nếu đầu vào giống như deadline =[1, 2, 2, 2] credit =[4, 5, 6, 7], thì đầu ra sẽ là 18, vì chúng ta có thể hoàn thành bài tập với tín chỉ 5 vào ngày 0, hoàn thành bài tập với tín chỉ 6 vào ngày 1 và hoàn thành bài tập với tín chỉ 7 vào ngày 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• a:=tạo một cặp thời hạn và tín dụng và sắp xếp chúng dựa trên tín dụng theo thứ tự giảm dần
• nếu a trống, thì
  • trả về 0
• res:=danh sách kích thước (1 + tối đa thời hạn) và điền bằng 0
• ans:=0
• cho mỗi cặp (i, j) trong a, do
  • cho k trong phạm vi tôi giảm xuống 0, giảm 1, thực hiện
    • nếu res [k] là 0, thì
      • res [k]:=1
      • ans:=ans + j
      • ra khỏi vòng lặp
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

class Solution:
   def solve(self, deadlines, credits):
      a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True)
      if not a:
         return 0
      res = [0] * (max(deadlines) + 1)
      ans = 0
      for i, j in a:
         for k in range(i, -1, -1):
            if not res[k]:
               res[k] = 1
               ans += j
               break
      return ans
     
ob = Solution()
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
print(ob.solve(deadlines, credits))

Đầu vào

[1, 2, 2, 2], [4, 5, 6, 7]

Đầu ra

18