找出Python竞赛中可达到的分数的程序

假设我们参加了一场编程竞赛，那里有多个问题，但是当我们解决一个问题时竞赛就结束了。现在，如果我们有两个长度相同的数字列表，称为点和机会。为了说明这一点，在这里针对第i个问题，我们有[i]％的机会可以解决它的点[i]点。我们还有另一个值k，它代表我们可以尝试的问题数量。不能两次尝试相同的问题。

如果我们设计出最佳策略，我们将必须找到比赛中可以得到的分数的期望值，并将其四舍五入为最接近的整数。我们可以将尝试第i个问题的值期望为points [i] *机会[i] / 100.0，这表示我们平均获得的点数。

因此，如果输入是点= [600、400、1000]，机会= [10、90、5]，k = 2，则输出将是392。

在线示例

让我们看下面的实现以更好地理解-

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