項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Lintcode】python – [800] Backpack IX 個人解法筆記

題目出處

800 · Backpack IX

難度

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102