পাইথনে একটি প্রতিযোগিতায় অর্জনযোগ্য পয়েন্ট খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা একটি প্রোগ্রামিং প্রতিযোগিতায় আছি যেখানে একাধিক সমস্যা আছে কিন্তু একটি সমস্যা সমাধান করলে প্রতিযোগিতা শেষ হয়। এখন যদি আমাদের কাছে একই দৈর্ঘ্যের সংখ্যার দুটি তালিকা থাকে যার নাম পয়েন্ট, এবং সম্ভাবনা। এটি ব্যাখ্যা করার জন্য, এখানে ith সমস্যাটির জন্য, আমাদের পয়েন্ট[i] পয়েন্টের জন্য এটি সমাধান করার সম্ভাবনা [i] শতাংশ সম্ভাবনা রয়েছে। আমাদের আরও একটি মান k আছে যা আমরা চেষ্টা করতে পারি এমন সমস্যার সংখ্যা উপস্থাপন করে। একই সমস্যা দুবার চেষ্টা করা যাবে না।

যদি আমরা একটি সর্বোত্তম কৌশল তৈরি করি, তাহলে প্রতিযোগিতায় আমরা যতগুলি পয়েন্ট পেতে পারি তার প্রত্যাশিত মান খুঁজে বের করতে হবে, যা নিকটতম পূর্ণসংখ্যাতে বৃত্তাকার। আমরা পয়েন্ট[i] * chances[i] / 100.0 হিসাবে ith সমস্যাটি চেষ্টা করার মান আশা করতে পারি, এবং এটি আমরা গড়ে কত পয়েন্ট পেতে পারি তা প্রতিনিধিত্ব করে।

সুতরাং, যদি ইনপুট হয় পয়েন্ট=[600, 400, 1000], সম্ভাবনা =[10, 90, 5], k =2, তাহলে আউটপুট হবে 392।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=পয়েন্টের আকার
0 থেকে n রেঞ্জের জন্য, করুন
সম্ভাবনা[i] :=সম্ভাবনা[i] / 100.0
R :=0-3 সাজানো বিন্দু অবতরণ অনুসারে সাজান
int(dp(0, K))
ফেরত দিন
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এর জন্য i, k
লাগবে
- যদি আমি n এর মত হয়, তাহলে
  - রিটার্ন 0.0
- j :=R[i]
- p :=সম্ভাবনা[j]
- 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