โปรแกรมค้นหาเครดิตสูงสุดที่เราจะได้จากการมอบหมายงานบางอย่างใน python

สมมติว่าเรามีสองรายการที่มีขนาดเท่ากัน นั่นคือกำหนดเวลาและหน่วยกิตและเป็นตัวแทนของการมอบหมายหลักสูตร กำหนดเวลา[i] แสดงวันครบกำหนดสำหรับการมอบหมายงาน i และหน่วยกิต[i] หมายถึงจำนวนหน่วยกิตที่เราได้รับสำหรับการมอบหมายงาน i เรามีเวลา 1 วันในการทำงานให้เสร็จ และสามารถดำเนินการให้แล้วเสร็จก่อนหรือภายในวันที่กำหนด เราไม่สามารถทำงานหลายงานพร้อมกันได้ เราต้องหาเครดิตสูงสุดที่เราจะได้จากการมอบหมายงานบางส่วนให้เสร็จ

ดังนั้นหากข้อมูลที่ป้อนเป็นเหมือนเส้นตาย =[1, 2, 2, 2] หน่วยกิต =[4, 5, 6, 7] ผลลัพธ์จะเป็น 18 เนื่องจากเราสามารถมอบหมายงานให้เสร็จสิ้นด้วยเครดิต 5 ในวันที่ 0 เสร็จสมบูรณ์ การมอบหมายด้วยเครดิต 6 ในวันที่ 1 และการมอบหมายงานด้วยเครดิต 7 ในวันที่ 3

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

• a :=ทำคู่ของกำหนดเวลาและเครดิตแล้วจัดเรียงตามเครดิตในลำดับจากมากไปน้อย
• ถ้า a ว่างเปล่า แล้ว
  • คืน 0
• res :=รายการขนาด (1 + สูงสุดของกำหนดเวลา) และเติมด้วย 0
• ตอบ :=0
• สำหรับแต่ละคู่ (i, j) ใน a, do
  • สำหรับ k ในช่วง i ลงไป 0, ลดลง 1 ทำ
    • ถ้า res[k] เป็น 0 แล้ว
      • res[k] :=1
      • ans :=ans + j
      • ออกมาจากวงจร
• คืนสินค้า

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

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

18