強盗をチェックするプログラムは、Pythonでボールトを奪うことができるかどうか

N人の強盗が金庫を奪おうとしていると仮定します。警備員がいましたが、G時間出かけた後、戻ってきます。また、各強盗にはボールトを奪う特定の時間がありますが、最大で2人が同時にボールトに入ることができます。問題は、彼らが警備員に捕まるボールトを奪うことができるかどうかをチェックする必要があるということです。そのことを覚えておく必要があります-

• 1人の強盗が時間tに金庫の中に入ると同時に、別の強盗が出てくる場合、彼らが同時に金庫にいなかったようです。

• 警備員が時間Gに金庫の中に入ると、強盗が時間Gに正確に出てきた場合、警備員は強盗に気づきません。

したがって、入力がN =3 G =5 time =[3,5,2]のようである場合、可能な配置が存在するため、出力はTrueになります。つまり-

• 時間t=0で、robber1は内部に入り、t=3で出てきます
• 時間t=0で、robber2は内部に入り、t=5で出てきます
• 時間t=3で、robber3が内部に入り、t=5で出てきます

これを解決するには、次の手順に従います-

• 時間内のすべての要素の合計が2*Gを超える場合、
  • Falseを返す
• それ以外の場合、時間内のすべての要素の合計<=Gの場合、
  • Trueを返す
• それ以外の場合、
  • 有効：=サイズG + 1の配列で、最初はすべての値がFalseです
  • valid [0]：=True
  • 時間内のxごとに、
    • Gから0の範囲のiの場合、1ずつ減らします。
      • i-x> =0かつvalid[i-x]の場合、
        • valid [i]：=True
  • 時間内のすべての要素の合計-範囲0のすべてのiの最大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))

入力

3,5,[3,5,2]

出力

True