Chương trình kiểm tra kẻ cướp có thể cướp kho tiền hay không bằng Python

Giả sử có N số tên cướp đang cố gắng cướp một kho tiền. Có một người bảo vệ nhưng anh ta đã ra ngoài trước giờ G, sau đó anh ta sẽ quay lại. Và mỗi tên cướp có thời gian cụ thể để cướp kho tiền, nhưng tối đa có thể có hai tên trong số chúng có thể vào cùng một lúc. Bây giờ vấn đề là chúng ta phải kiểm tra xem chúng có cướp được kho tiền khi bị bảo vệ bắt hay không? Chúng tôi phải ghi nhớ rằng -

• Nếu một tên cướp đi vào bên trong hầm cùng lúc và cùng lúc một tên cướp khác bước ra, thì giống như chúng chưa bao giờ ở trong hầm cùng một lúc.

• Nếu người bảo vệ vào bên trong hầm vào lúc G và một tên cướp xuất hiện đúng lúc G, người bảo vệ sẽ không nhận thấy tên cướp.

Vì vậy, nếu đầu vào là N =3 G =5 time =[3,5,2], thì đầu ra sẽ là Đúng, vì có thể có sự sắp xếp ở đó, tức là -

• tại thời điểm t =0, robber1 vào trong và đi ra tại t =3
• tại thời điểm t =0, robber2 vào trong và đi ra tại t =5
• tại thời điểm t =3, robber3 vào trong và đi ra tại t =5

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu tổng tất cả các phần tử trong thời gian> 2 * G, thì
  • trả về Sai
• ngược lại khi tổng của tất cả các phần tử trong thời gian <=G, thì
  • trả về True
• nếu không,
  • hợp lệ:=một mảng có kích thước G + 1 và ban đầu tất cả các giá trị đều là Sai
  • hợp lệ [0]:=True
  • đối với mỗi x trong thời gian, thực hiện
    • đối với tôi trong phạm vi G thành 0, giảm đi 1, thực hiện
      • nếu i-x> =0 và hợp lệ [i-x], thì
        • hợp lệ [i]:=True
  • nếu tổng của tất cả các phần tử trong thời gian - tối đa của i đối với mọi i trong phạm vi 0 đến kích thước là hợp lệ khi hợp lệ [i] <=G, thì
    • trả về True
  • nếu không,
    • trả về Sai

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

3,5,[3,5,2]

Đầu ra

True