Python中找出竞赛中可获得的分数的程序

假设我们参加一个程序设计竞赛，其中有多个问题，但我们只要解决一个问题就可以结束竞赛。现在，如果我们有两个长度相同的数字列表，其中一个列表是称为“points”，另一个列表是称为“chances”，为了解释清楚，这里的第i个问题，我们有一个s[i]％的概率解决它，得分为points[i]。我们还有一个值k，它表示我们可以尝试的问题数目。不能尝试同一个问题两次。

如果我们设计一种最佳策略，我们将不得不找到我们可以在竞赛中获得的积分数的期望值，四舍五入为最接近的整数。我们可以期望第i个问题的价值为points[i] * chances[i] / 100.0，这表示我们平均可以获得的积分数。

所以，如果输入如下：points = [600, 400, 1000]，chances = [10, 90, 5]，k = 2，则输出将为392。

为了解决这个问题，我们将按照以下步骤进行：

n：points的大小
对于i在0到n的范围内，执行以下操作：
chances[i]：=chances[i] /100.0
R：将0-3按照点数降序排列
int(dp(0，K))
定义函数dp()，它将包含i和k
- 如果i与n相同，则
  - 返回0.0
- j：=R[i]
- p：=chances[j]
- ev：=p *points[j]
- 如果k等于1，则
  - 返回ev和dp(i +1，k)中的最大值
- 返回dp(i +1，k -1) *（1-p）+ev和dp(i +1，k)中的最大值

更多Python相关文章，请阅读：Python 教程

示例

让我们看以下实现以更好地理解：

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))