โปรแกรมตรวจสอบว่าสามารถรันงานทั้งหมดด้วยโคร์เซิร์ฟเวอร์ที่มีได้หรือไม่ใน Python

สมมติว่าเรามีสองรายการ คือ cores และ tasks โดย cores[i] แสดงจำนวนโคร์ที่มีในเซิร์ฟเวอร์ตัวที่ i และ tasks[i] แสดงจำนวนโคร์ที่ต้องใช้รันงานตัวนั้น แต่ละงานต้องรันบนเซิร์ฟเวอร์เพียงตัวเดียว แตเซิร์ฟเวอร์หนึ่งอาจรันงานได้หลายงาน เราต้องตรวจสอบว่าสามารถรันงานทั้งหมดด้วยโคร์ที่มีได้หรือไม่

เช่น ถ้าอินพุตคือ cores = [10, 7], tasks = [7, 3, 2, 2, 1] ผลลัพธ์จะเป็น True เพราะสามารถวาง tasks[0] และ tasks[1] ในเซิร์ฟเวอร์แรก (โคร์ 10) และงานที่เหลือในเซิร์ฟเวอร์ที่สอง (โคร์ 7)

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

1. กำหนดฟังก์ชัน solve(cores, tasks):
   • ถ้า tasks ว่าง คืนค่า True
   • สำหรับ i ในช่วง 0 ถึง ขนาดของ cores - 1:
     • ถ้า cores[i] >= tasks[0]:
       • cores[i] := cores[i] - tasks[0]
       • ถ้า solve(cores, tasks[1:]) เป็นจริง คืนค่า True
       • cores[i] := cores[i] + tasks[0] (backtrack)
   • คืนค่า False

ตัวอย่างการใช้งาน

def solve(cores, tasks):
    if not tasks:
        return True
    for i in range(len(cores)):
        if cores[i] >= tasks[0]:
            cores[i] -= tasks[0]
            if solve(cores, tasks[1:]):
                return True
            cores[i] += tasks[0]
    return False

cores = [10, 7]
tasks = [7, 3, 2, 2, 1]
print(solve(cores, tasks))

อินพุต

[10, 7], [7, 3, 2, 2, 1]

เอาต์พุต

True