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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告