題目出處

562 · Backpack IV

難度

medium

個人範例程式碼

from typing import (
    List,
)

class Solution:
    """
    @param nums: an integer array and all positive numbers, no duplicates
    @param target: An integer
    @return: An integer
    """
    def back_pack_i_v(self, nums: List[int], target: int) -> int:
        # write your code here
        if not nums:
            return 0

        dp = [0 for _ in range(target+1)]
        dp[0] = 1

        nums.sort()
        for num in nums: # take new category by ascending
            for current_target in range(target+1):
                last_target_before_take_this_coin = current_target - num
                if last_target_before_take_this_coin >= 0:
                    dp[current_target] += dp[last_target_before_take_this_coin]

        return dp[-1]

算法說明

本題是背包系列問題的第 4 題，建議初學者可以從第一題開始去學：
第 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()

外圈 for 一樣的是我們控制目前最大的容量
內圈 for 我們去控制目前新拿的物品種類

dp 的運作

初始化一樣 dp[0] = 1
last_volume = current_volume – size
如果 last_volume >= 0， dp[current_volume] += dp[last_volume] # 表示新增的可能性 (因為順序有先 sort 過，剛好會是直接排好的結果)

例如：

• dp[3] += dp[2] (dp[2] 的所有可能性 + 1 size)
• dp[3] += dp[1] (dp[1] 的所有可能性 + 2 size)

input handling

如果沒有 nums，回傳 0，
其他一同在 dp 內處理

Boundary conditions

用兩層 for 來控制搜尋範圍，
外層 for volume (表示我們目前背包的大小，最大可能的價值)
內層 for value (表示新增「一個」新的種類後，保留目前容量可能的所有可能組合)

Reference