題目出處
難度
medium
個人範例程式碼
from typing import (
List,
)
class Solution:
"""
@param n: Your money
@param prices: Cost of each university application
@param probability: Probability of getting the University's offer
@return: the highest probability
"""
def backpack_i_x(self, n: int, prices: List[int], probability: List[float]) -> float:
# write your code here
# probability of receiving at least one offer = 1 - "(not get offer * not get offer * ...)" <- we record minimum of this
dp = [[1] * (n+1) for _ in range(2)] # record no offer probability
for i in range(1, len(prices)+1):
for j in range(1, n+1):
dp[i%2][j] = dp[(i-1)%2][j]
last_cost = j - prices[i-1]
if last_cost >= 0:
no_offer_prob = dp[(i-1)%2][last_cost] * (1 - probability[i-1])
dp[i%2][j] = min(dp[i%2][j], no_offer_prob)
# print(dp)
ans = 0
for each_price_no_offer_prob in dp[len(prices)%2]:
ans = max(ans, 1 - each_price_no_offer_prob)
return ans
算法說明
本題是背包系列問題的第 9 題,建議初學者可以從第一題開始去學:
第 1 題:最基本的背包問題,不重複 size,物品只有一個,計算組合可能性
第 2 題:最基本的背包問題,不重複 size,物品只有一個,計算最大價值
第 3 題:完全背包問題,有重複 size,物品無限數量,計算最大價值
第 4 題:有重複 size,物品無限數量,計算可能組合 ,「(1,2,3) 與 (2,3,1) 視為相同答案」
第 5 題:有重複 size,物品有限數量,計算可能組合 ,「(1,2,3) 與 (2,3,1) 視為相同答案」
第 6 題:有重複 size,物品無限數量,計算可能「排列」 ,也就是說「(1,2,3) 與 (2,3,1) 視為不同答案」
第 7 題:有重複物品,有限制物品數數量上限,問可能組合
第 8 題:有重複物品,有限制物品數數量上限,問最大價值
第 9 題:變化問題,有重複 size,計算機率
第 10 題:變化問題,只是把 size 面額提高
第九題,我們一間公司最多可以選一次,屬於變化題型的一種,大概念與之前相同。
這題我們要算的是「只少拿到一間公司 offer 的成功機率」,
我們先嘗試推導公式 = 「1 – (沒拿到公司 offer 的機率) * (沒拿到公司 offer 的機率) * (沒拿到公司 offer 的機率) …」
其中,「(沒拿到公司 offer 的機率)」= 「1 – 「(拿到公司 offer 的機率)」」
為了我們處理方便,我們在 dp 中記錄下 「min((沒拿到公司 offer 的機率) * (沒拿到公司 offer 的機率) * (沒拿到公司 offer 的機率))…」 的這一段。
外圈 for 我們新發現的公司
內圈 for 控制我們目前使用的金錢
優化空間 – 滾動數組
這裡我們先放上優化前的 code (會有「空間超過的問題」)
from typing import (
List,
)
class Solution:
"""
@param n: Your money
@param prices: Cost of each university application
@param probability: Probability of getting the University's offer
@return: the highest probability
"""
def backpack_i_x(self, n: int, prices: List[int], probability: List[float]) -> float:
# write your code here
# probability of receiving at least one offer = 1 - "(not get offer * not get offer * ...)" <- we record minimum of this
dp = [[1] * (n+1) for _ in range(len(prices)+1)] # record no offer probability
for i in range(1, len(prices)+1):
for j in range(1, n+1):
dp[i][j] = dp[i-1][j]
last_cost = j - prices[i-1]
if last_cost >= 0:
no_offer_prob = dp[i-1][last_cost] * (1 - probability[i-1])
dp[i][j] = min(dp[i][j], no_offer_prob)
# print(dp)
ans = 0
for each_price_no_offer_prob in dp[-1]:
ans = max(ans, 1 - each_price_no_offer_prob)
return ans
我們仔細觀察我們 dp 的運算過程,基本上每一層新的 dp[i][],
我們都只會參考 dp[i-1][] 的資料而已,(也就說,我們只參考前一層),
因此我們可以利用這個特性節省空間,宣告空間 i = 2 即可,
而取 i 的變化時,我們取 mod 2,
最後的答案就位於 dp[n%2][volume] 中。
input handling
如果沒有 nums,回傳 0,
其他一同在 dp 內處理
Boundary conditions
用兩層 for 來控制搜尋範圍,
外層 for 發現一間新的公司 (表示這間新的公司,我們決定去或不去有可能有哪些組合。)
內層 for 使用的金錢 (表示我們目前花了多少錢)
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 |