Python程式：計算競賽中可獲得的積分

假設我們參加一個程式設計競賽，其中有多個問題，但當我們解決一個問題時，競賽就結束。現在，如果我們有兩個相同長度的數字列表，分別稱為 points 和 chances。為了解釋它，對於第 i 個問題，我們有 chances[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 按照 points 降序排列

  • 返回 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) 的最大值

示例

讓我們看看以下實現以獲得更好的理解：

即時演示

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

更新於: 2020-12-23

142 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告