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

สมมุติว่าเรามี 2 รายการ คือ cores และ task cores[i] ระบุจำนวนคอร์ที่มีอยู่ในเซิร์ฟเวอร์ ith และงาน[i] ระบุจำนวนคอร์ที่จำเป็นในการดำเนินงานนั้น แต่ละงานต้องรันในเซิร์ฟเวอร์เดียวเท่านั้น และเซิร์ฟเวอร์อาจมีงานหลายอย่างที่ต้องดำเนินการ เราต้องตรวจสอบว่าเป็นไปได้หรือไม่ที่จะรันงานทั้งหมดด้วยคอร์ที่กำหนดหรือไม่

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

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

• กำหนดฟังก์ชัน Solve() สิ่งนี้จะใช้เวลาหลัก งาน
• ถ้าชุดงานว่างเปล่า
  • คืนค่า True
• สำหรับฉันในช่วง 0 ถึงขนาดของคอร์ - 1 ทำ
  • ถ้า cores[i]>=งาน[0] แล้ว
    • cores[i] :=cores[i] - งาน[0]
  • ถ้าแก้(คอร์, รายการงานยกเว้นงานแรก) เป็นจริง แล้ว
    • คืนค่า True
  • คอร์[i] :=คอร์[i] + งาน[0]
• คืนค่าเท็จ

ตัวอย่าง

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

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