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

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

เช่น deadlines = [1, 2, 2, 2] credits = [4, 5, 6, 7] ผลลัพธ์ 18 เพราะทำงานเครดิต 5 วันที่ 0, เครดิต 6 วันที่ 1, เครดิต 7 วันที่ 3

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

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

ตัวอย่างโค้ด

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