Giả sử chúng ta đang tham gia một cuộc thi lập trình trong đó có nhiều vấn đề nhưng cuộc thi kết thúc khi chúng ta giải quyết được một vấn đề. Bây giờ nếu chúng ta có hai danh sách các số có cùng độ dài được gọi là điểm và cơ hội. Để giải thích nó, ở đây đối với bài toán thứ i, chúng ta có [i] phần trăm cơ hội giải được nó với số điểm [i] điểm. Chúng ta cũng có một giá trị k khác đại diện cho số vấn đề mà chúng ta có thể thử. Không thể thử cùng một vấn đề hai lần.
Nếu chúng tôi đề ra một chiến lược tối ưu, chúng tôi sẽ phải tìm giá trị kỳ vọng của số điểm chúng tôi có thể nhận được trong cuộc thi, giá trị này được làm tròn đến số nguyên gần nhất. Chúng ta có thể kỳ vọng giá trị của việc thử giải bài toán thứ i là điểm [i] * cơ hội [i] / 100,0 và điều này thể hiện số điểm trung bình mà chúng ta sẽ nhận được.
Vì vậy, nếu đầu vào giống như điểm =[600, 400, 1000], cơ hội =[10, 90, 5], k =2, thì đầu ra sẽ là 392.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của điểm
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
cơ hội [i]:=cơ hội [i] / 100,0
-
R:=sắp xếp 0-3 được sắp xếp theo điểm giảm dần
-
trả về int (dp (0, K))
-
Định nghĩa một hàm dp (). Điều này sẽ mất tôi, k
-
nếu tôi giống n, thì
-
trả về 0,0
-
-
j:=R [i]
-
p:=cơ hội [j]
-
ev:=p * điểm [j]
-
nếu k giống với 1 thì
-
trả về tối đa ev, dp (i + 1, k)
-
-
trả về tối đa dp (i + 1, k - 1) * (1 - p) + ev, dp (i + 1, k)
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[600, 400, 1000], [10, 90, 5], 2
Đầu ra
392