題目出處
難度
medium
個人範例程式碼
from typing import (
List,
)
class Solution:
"""
@param nums: an integer array and all positive numbers
@param target: An integer
@return: An integer
"""
def back_pack_v(self, nums: List[int], target: int) -> int:
# write your code here
if not nums:
return 0
# [1,1,1,1] has 4 ans, remove 1 has 4 choice
n = len(nums)
dp = [[0] * (target +1) for _ in range(2)]
dp[0][0] = 1
prefix_sum = 0
for i in range(1, n+1): # take next category of coin
dp[i%2][0] = 1
prefix_sum += nums[i-1]
for j in range(1, min(target, prefix_sum)+1): # find current max
dp[i%2][j] = dp[(i-1)%2][j]
last_volume = j - nums[i-1]
if last_volume >= 0: # add take new one coin method
dp[i%2][j] += dp[(i-1)%2][last_volume]
return dp[n%2][target]
算法說明
本題是背包系列問題的第 5 題，建議初學者可以從第一題開始去學：
第 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 面額提高
第五題，我們變成只有有限數量的物品可以拿，求可能的方法總數。
因為拿的順序會影響結果，例如：「(2,2,3) 與 (3,2,2) 是同一個結果」，
我們一開始就先 nums.sort()
但這邊要注意陷阱「同 size 的不同物品，是為不同組合」，例如： [1,1,1,1], target = 3，要算 4 個結果 (可以想像我們是在決定拿掉哪一個)。
外圈 for 我們去控制目前新拿的物品種類
內圈 for 控制目前背包最大的容量
dp 的運作
dp[i][j]，j 代表目前的大小，i 反映我們目前選擇的物件。
優化空間 - 滾動數組
這裡我們先放上優化前的 code (會有「空間超過的問題」)
from typing import (
List,
)
class Solution:
"""
@param nums: an integer array and all positive numbers
@param target: An integer
@return: An integer
"""
def back_pack_v(self, nums: List[int], target: int) -> int:
# write your code here
if not nums:
return 0
# [1,1,1,1] has 4 ans, remove 1 has 4 choice
n = len(nums)
dp = [[0] * (target +1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1): # take next category of coin
dp[i][0] = 1
for j in range(1, target+1):
dp[i][j] = dp[i-1][j]
last_volume = j - nums[i-1]
if last_volume >= 0: # add take new one coin method
dp[i][j] += dp[i-1][last_volume]
return dp[-1][-1]
我們仔細觀察我們 dp 的運算過程，基本上每一層新的 dp[i][]，
我們都只會參考 dp[i-1][] 的資料而已，(也就說，我們只參考前一層)，
因此我們可以利用這個特性節省空間，宣告空間 i = 2 即可，
而取 i 的變化時，我們取 mod 2，
最後的答案就位於 dp[n%2][volume] 中。
小優化時間
在內層的 for 迴圈，我們其實每次不一定有必要都算到 target 那麼大，
我們可以知道，多一個新的物品，最大可能的 size 就是前面全選的合。
因此，在內層的 for 迴圈中，
我們可以多取一個 「min(target, prefix_sum) + 1」，
可以節省大量的明明算不到 target，卻總是算到 target 位置的時間。
input handling
如果沒有 nums，回傳 0，
其他一同在 dp 內處理
Boundary conditions
用兩層 for 來控制搜尋範圍，
外層 for size (表示這個新的物品，我們決定拿與不拿有可能有哪些組合。)
內層 for volume (表示我們目前背包的大小)