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

假设有N个强盗试图抢劫保险库。本来有个警卫，但他外出了G个时间，之后他会回来。每个强盗有特定的时间抢劫保险库，但最多只有两个人可以同时进入保险库。现在问题是我们必须检查他们是否能够抢劫保险库而不被警卫抓住？我们必须记住一点−

如果有一个强盗在t时间进入保险库，同时另一个强盗在同一时间出来，那么就像他们没有同时在保险库里一样。
如果警卫在G时间进入保险库，而一名强盗正好在时间G出来，那么警卫不会注意到这个强盗。

因此，如果输入如N = 3 G = 5 time = [3,5,2]，则输出将为True，因为存在可能的安排，即−

在时间t = 0，抢劫犯1进入并在t = 3时出来
在时间t = 0，抢劫犯2进入并在t = 5时出来
在时间t = 3，抢劫犯3进入并在t = 5时出来

要解决这个问题，我们将按照以下步骤进行−

如果time中所有元素的和> 2 * G，则
- 返回False
否则，当time中所有元素的总和<= G时，则
- 返回True
否则，
- valid：初始大小为G + 1的数组，所有值最初都为False
- valid [0]：True
- 对于time中的每个x，执行以下操作
  - 对于i在G范围内的每个x，递减1，执行以下操作
  - 如果i-x> = 0并且valid [i-x]，则
    - valid [i]：True
- 如果time中所有元素的和 – 对于所有范围在0到valid大小之间的i的最大值时，当valid [i] <= G时，则
  - 返回True
- 否则，
  - 返回False

例

让我们看下面的实现，以获得更好的理解−

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