โปรแกรมเพื่อค้นหาคะแนนที่ทำได้ในการแข่งขันใน Python

สมมติว่าเราอยู่ในการแข่งขันการเขียนโปรแกรมที่มีปัญหาหลายอย่าง แต่การแข่งขันจะสิ้นสุดลงเมื่อเราแก้ปัญหาหนึ่งปัญหา ทีนี้ ถ้าเรามีสองรายการของตัวเลขที่มีความยาวเท่ากัน เรียกว่า จุด และโอกาส เพื่ออธิบายสิ่งนี้สำหรับปัญหาที่ ith เรามีโอกาสเปอร์เซ็นต์ [i] โอกาสในการแก้ปัญหานี้สำหรับคะแนน[i] นอกจากนี้เรายังมีค่า k อีกค่าหนึ่งซึ่งแสดงถึงจำนวนปัญหาที่เราสามารถลองได้ ไม่สามารถลองปัญหาเดิมซ้ำ 2 ครั้งได้

หากเราวางแผนกลยุทธ์ที่เหมาะสม เราจะต้องหาค่าที่คาดหวังจากจำนวนคะแนนที่เราจะได้ในการแข่งขัน ซึ่งจะถูกปัดเศษให้เป็นจำนวนเต็มที่ใกล้เคียงที่สุด เราสามารถคาดหวังมูลค่าของการพยายามแก้ปัญหาด้วยคะแนน[i] * โอกาส[i] / 100.0 ซึ่งแสดงถึงจำนวนคะแนนที่เราจะได้รับโดยเฉลี่ย

ดังนั้น หากอินพุตเท่ากับ points=[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