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

मान लीजिए 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 के लिए, करें
    • i को G से 0 तक, 1 से घटाते हुए, करें
      • यदि i-x >= 0 और valid[i-x], तो
        • valid[i] := True
  • यदि time में सभी तत्वों का योग - उन सभी 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