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，执行
      • 对于从G到0的范围i，递减1，执行
        • 如果i-x >= 0且valid[i-x]，则
          • valid[i] := True
    • 如果time中所有元素的总和 - valid[i]为True时，从0到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))

输入

3,5,[3,5,2]

输出

True

更新于: 2021年10月23日

69 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告