用 Python 编写程序检查强盗是否可以抢劫保险库

pythonserver side programmingprogramming更新于 2026/1/30 15:08:17

假设有 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出来

为了解决这个问题，我们将遵循以下步骤 −

如果时间中所有元素的总和 > 2*G，则
- 返回 False
否则，当时间中所有元素的总和 <= G 时，则
- 返回 True
否则，
- valid := 大小为 G + 1 的数组，并且最初所有值均为 False
- valid[0] := True
- 对于时间中的每个 x，执行
  - 对于范围从 G 到 0 的 i，减少 1，执行
    - 如果 i-x >= 0 且 valid[i-x]，则
      - valid[i] := True
- 如果所有元素的总和时间中的元素 - 当 valid[i] <= G 时，对于 0 到 valid 大小范围内的所有 i，i 的最大值，则
  - 返回 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))