पायथन में लुटेरों की जाँच करने का कार्यक्रम तिजोरी को लूट सकता है या नहीं

मान लीजिए कि एन संख्या में लुटेरे एक तिजोरी को लूटने की कोशिश कर रहे हैं। एक गार्ड था लेकिन वह G समय के लिए बाहर गया, उसके बाद वह वापस आ जाएगा। और प्रत्येक लुटेरे के पास तिजोरी को लूटने का विशिष्ट समय होता है, लेकिन उनमें से अधिक से अधिक दो एक ही समय में तिजोरी में प्रवेश कर सकते हैं। अब समस्या यह है कि हमें यह जांचना होगा कि क्या वे गार्ड द्वारा पकड़े जाने की तिजोरी को लूट सकते हैं? हमें यह ध्यान रखना होगा कि -

• अगर एक समय में एक डाकू तिजोरी के अंदर जाता है और उसी समय दूसरा लुटेरा बाहर आता है, तो ऐसा लगता है जैसे वे एक ही समय में तिजोरी में कभी नहीं थे।

• यदि गार्ड G समय पर तिजोरी के अंदर पहुँच जाता है और एक डाकू ठीक G समय पर बाहर आता है, तो गार्ड डाकू को नोटिस नहीं करेगा।

इसलिए, यदि इनपुट एन =3 जी =5 समय =[3,5,2] जैसा है, तो आउटपुट सही होगा, क्योंकि संभावित व्यवस्था है, यानी -

• t=0 समय पर, डाकू1 अंदर जाता है और t=3 पर बाहर आता है
• t=0 समय पर, डाकू2 अंदर जाता है और t=5 पर बाहर आता है
• t=3 समय पर, डाकू3 अंदर जाता है और t=5 पर बाहर आता है

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• यदि समय में सभी तत्वों का योग> 2*G, तो
  • झूठी वापसी
• अन्यथा जब समय में सभी तत्वों का योग <=G, तब
  • सही लौटें
• अन्यथा,
  • मान्य :=आकार G + 1 की एक सरणी, और प्रारंभ में सभी मान गलत हैं
  • वैध[0] :=सच
  • प्रत्येक x समय के लिए, करें
    • मैं के लिए जी से 0 की सीमा में, 1 से घटाएं
      • यदि i-x>=0 और मान्य[i-x], तो
        • वैध[i] :=सच
  • यदि समय में सभी तत्वों का योग - अधिकतम मैं सभी के लिए मैं सीमा 0 में मान्य के आकार के लिए जब वैध [i] <=जी, तो
    • सही लौटें
  • अन्यथा,
    • झूठी वापसी

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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