題目出處
難度
medium
個人範例程式碼
from typing import (
List,
)
class Solution:
"""
@param n: the value from 1 - n
@param value: the value of coins
@param amount: the number of coins
@return: how many different value
"""
def back_pack_v_i_i_i(self, n: int, value: List[int], amount: List[int]) -> int:
# write your code here
m = len(value)
dp = [False for _ in range(n+1)]
dp[0]= True
current_max_value = 0
ans = 0
for i in range(1, m+1):
cnt = [0 for _ in range(n+1)]
current_max_value += amount[i-1] * value[i-1]
for current_value in range(min(n, current_max_value)+1):
last_value = current_value - value[i-1]
if last_value >= 0 and dp[last_value] and (not dp[current_value]) and cnt[last_value] < amount[i-1]: # only found dp[last_value] True, dp[current_value] False
ans += 1
cnt[current_value] = cnt[last_value] + 1
dp[current_value] = dp[current_value] or dp[last_value]
# print(cnt)
# print(dp)
return ans
算法說明
本題是背包系列問題的第 7 題，建議初學者可以從第一題開始去學：
第 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,4]*[3,1] 直接看做 [2,2,2,4] 來處理，也許會更容易 (就能夠比照單一數量的題目辦理)。
不過處理上這題會有時間要求，如果直接無腦三層 for 迴圈，會發生 TLE。
因此我們會需要做一些修改。
我們可以把同個元素視為一組，再一次 O(n) 運算中就全部算完。
三層 for 我們會要花 O(n^2) 的時間才算得完，使花的時間增加不少。
- 同時優化空間與時間的版本：
我們只有一個 dp，配上一個我們新宣告的 cnt 作為我們的計數器，
而我們只在 dp[last] = T 且 dp[current] = F 進行操作，理由是：
- dp[last] = T，理由是我們本來就應該要確認，先前的數值是組的出來的。
- dp[current] = F，理由是我們要排除 1+1, 2 這樣計數器會被增加的情況，實際上我們不需要用 2 就組得出來
三層 for 迴圈的解法 – 會 TLE
這題如果無腦三層 for 迴圈的寫法，會觸發 TLE，導致不能通過。
運算邏輯比較簡單，我們可以參考下圖：
或者以下列的方式理解：
以下就是三層 for 迴圈的程式碼 – 會 TLE
from typing import (
List,
)
class Solution:
"""
@param n: the value from 1 - n
@param value: the value of coins
@param amount: the number of coins
@return: how many different value
"""
def back_pack_v_i_i_i(self, n: int, value: List[int], amount: List[int]) -> int:
# write your code here
m = len(value)
dp = [[False] *(n+1) for _ in range(2)]
num_of_selected_items = 0
dp[num_of_selected_items][0]= True
current_max_value = 0
for i in range(m):
for get_i_amount in range(1, amount[i]+1): # get j amount
num_of_selected_items += 1
dp[num_of_selected_items%2][0]= True # init
current_max_value += value[i]
for current_value in range(min(n, current_max_value)+1): # need update: from 0 to min(n, current_max_value)+1, current_max_value = we take all thing's value
dp[num_of_selected_items%2][current_value] = dp[(num_of_selected_items-1)%2][current_value]
last_value = current_value - value[i]
if last_value >= 0:
dp[num_of_selected_items%2][current_value] = dp[num_of_selected_items%2][current_value] or dp[(num_of_selected_items-1)%2][last_value]
# print(num_of_selected_items, dp)
# print(dp[num_of_selected_items%2])
cnt = 0
for value in range(1, n+1):
if dp[num_of_selected_items%2][value]:
cnt += 1
return cnt
input handling
一同在 dp 內處理