पायथन में एक प्रतियोगिता में प्राप्त अंक का पता लगाने के लिए कार्यक्रम

मान लीजिए कि हम एक प्रोग्रामिंग प्रतियोगिता में हैं जहां कई समस्याएं हैं लेकिन जब हम एक समस्या का समाधान करते हैं तो प्रतियोगिता समाप्त हो जाती है। अब यदि हमारे पास समान लंबाई की संख्याओं की दो सूचियाँ हैं जिन्हें अंक और संभावनाएँ कहते हैं। इसे समझाने के लिए, यहाँ ith समस्या के लिए, हमारे पास अंक [i] अंक के लिए इसे हल करने का एक मौका [i] प्रतिशत मौका है। हमारे पास एक अन्य मान k भी है जो हमारे द्वारा प्रयास की जा सकने वाली समस्याओं की संख्या को दर्शाता है। एक ही समस्या का दो बार प्रयास नहीं किया जा सकता है।

यदि हम एक इष्टतम रणनीति तैयार करते हैं, तो हमें प्रतियोगिता में जितने अंक प्राप्त हो सकते हैं, उसका अपेक्षित मूल्य ज्ञात करना होगा, जो कि निकटतम पूर्णांक तक होता है। हम अंक के रूप में ith समस्या का प्रयास करने के मूल्य की उम्मीद कर सकते हैं [i] * संभावना [i] / 100.0, और यह उन अंकों की संख्या को दर्शाता है जो हमें औसतन प्राप्त होंगे।

इसलिए, यदि इनपुट अंक =[600, 400, 1000], संभावना =[10, 90, 5], के =2 जैसा है, तो आउटपुट 392 होगा।

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

• n :=बिंदुओं का आकार

• मेरे लिए 0 से n की सीमा में, करें

• चांस [i] :=चांस [i] / 100.0

• R :=0-3 को अवरोही बिंदुओं के अनुसार क्रमबद्ध करें

• वापसी int(dp(0, K))

• एक फ़ंक्शन को परिभाषित करें dp() । यह ले जाएगा मैं, के

  • अगर मैं n के समान हूं, तो

    • वापसी 0.0

  • जे:=आर[i]

  • पी:=चांस [जे]

  • ev :=p * अंक[j]

  • अगर k 1 के समान है, तो

    • ev, dp(i + 1, k) की अधिकतम वापसी करें

  • अधिकतम dp(i + 1, k-1) *(1 - p) + ev, dp(i + 1, k)

    लौटाएं

उदाहरण

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

class Solution:
   def solve(self, points, chances, K):
      n = len(points)
      for i in range(n):
         chances[i] /= 100.0
      R = sorted(range(n), key=points.__getitem__, reverse=True)
      def dp(i, k):
         if i == n:
            return 0.0
         j = R[i]
         p = chances[j]
         ev = p * points[j]
         if k == 1:
            return max(ev, dp(i + 1, k))
         return max(dp(i + 1, k - 1) * (1 - p) + ev, dp(i + 1, k))
      return int(dp(0, K))

ob = Solution()
print (ob.solve([600, 400, 1000], [10, 90, 5], 2))

इनपुट

[600, 400, 1000], [10, 90, 5], 2

आउटपुट

392