在 Python 中检查强盗是否可以抢劫金库的程序

假设有 N 个劫匪试图抢劫金库。有一个守卫，但他出去了G时间，之后他会回来。而且每个强盗都有特定的时间来抢金库，但最多只能有两个人同时进入金库。现在的问题是我们要检查他们是否可以抢劫被守卫抓住的金库？我们必须记住 -

• 如果一个强盗在时间 t 进入金库，同时另一个强盗出来，那么就好像他们从未在同一时间进入金库。

• 如果守卫在 G 时间进入保险库并且强盗恰好在 G 时间出来，守卫将不会注意到强盗。

因此，如果输入像 N = 3 G = 5 次 = [3,5,2]，那么输出将为 True，因为存在可能的安排，即 -

• 在 t=0 时刻，robber1 进去，在 t=3 时刻出来

• 在时间 t=0 时，robber2 进入并在 t=5 时出来

• 在时间 t=3 时，robber3 进入并在 t=5 时出来

示例

让我们看看以下实现以获得更好的理解 -

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