โปรแกรมตรวจสอบโจรปล้นห้องนิรภัยได้หรือไม่ใน Python

สมมติว่ามีโจรจำนวน N ที่พยายามจะปล้นห้องนิรภัย มียามเฝ้าแต่ออกไปสักระยะหนึ่งแล้วจะกลับมา และโจรแต่ละคนมีเวลาเฉพาะเจาะจงในการปล้นห้องนิรภัย แต่อย่างน้อยสองคนสามารถเข้าไปในหลุมฝังศพได้พร้อมกัน ตอนนี้ปัญหาคือเราต้องตรวจสอบว่าพวกเขาสามารถขโมยตู้นิรภัยจากการถูกยามจับได้หรือไม่? เราต้องจำไว้ว่า -

• หากโจรคนหนึ่งเข้าไปในห้องนิรภัยทีละคน และในขณะเดียวกันก็มีโจรอีกคนหนึ่งออกมา แสดงว่าพวกเขาไม่เคยอยู่ในห้องนิรภัยพร้อมกัน

• หากยามเข้าไปในหลุมฝังศพในเวลา G และโจรออกมาตรงเวลา G ผู้คุมจะไม่สังเกตเห็นโจร

ดังนั้น หากอินพุตเป็น N =3 G =5 เวลา =[3,5,2] ผลลัพธ์จะเป็น True เพราะการจัดเรียงที่เป็นไปได้อยู่ที่นั่น นั่นคือ −

• ในเวลา t=0, โจร1 เข้าไปข้างในและออกมาที่ t=3
• ในเวลา t=0, โจร2 เข้าไปข้างในและออกมาที่ t=5
• เมื่อถึงเวลา t=3 โจร 3 เข้าไปข้างในและออกมาที่ t=5

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

• ถ้าผลรวมขององค์ประกอบทั้งหมดในเวลา> 2*G แล้ว
  • คืนค่าเท็จ
• มิฉะนั้น เมื่อผลรวมขององค์ประกอบทั้งหมดในเวลา <=G แล้ว
  • คืนค่า True
• มิฉะนั้น
  • ถูกต้อง :=อาร์เรย์ขนาด G + 1 และเริ่มต้นค่าทั้งหมดเป็นเท็จ
  • ถูกต้อง[0] :=จริง
  • สำหรับ x แต่ละครั้ง ทำ
    • สำหรับฉันในช่วง G ถึง 0, ลดลง 1 ทำ
      • ถ้า i-x>=0 และ valid[i-x] แล้ว
        • ถูกต้อง[i] :=จริง
  • ถ้าผลรวมขององค์ประกอบทั้งหมดในเวลา - สูงสุดของ i สำหรับ i ทั้งหมดในช่วง 0 ถึงขนาดที่ถูกต้องเมื่อ valid[i] <=G แล้ว
    • คืนค่า True
  • มิฉะนั้น
    • คืนค่าเท็จ

ตัวอย่าง

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

def solve(N, G, time):
   if sum(time) > 2*G:
      return False
   elif sum(time) <= G:
      return True
   else:
      valid = [False]*(G+1)
      valid[0] = True
      for x in time:
         for i in range(G,-1,-1):
            if i-x >= 0 and valid[i-x]:
               valid[i] = True
      if sum(time) - max(i for i in range(len(valid)) if valid[i]) <= G:
         return True
      else:
         return False

N = 3
G = 5
time = [3,5,2]
print(solve(N, G, time))

อินพุต

3,5,[3,5,2]

ผลลัพธ์

True