Knapsack DP ·

介紹
#

Knapsack DP 題目表面很像，但正確解法取決於三個問題：

每個 item 只能用一次，還是可以重複使用？
dp[...] 代表 reachable、ways、minimum cost，還是 maximum value？
做 1D compression 時，capacity loop 要往後還是往前？

大部分錯誤都來自這三個問題其中一個答錯。

0/1 Knapsack
#

每個 item 最多只能用一次，所以壓縮成 1D 後，capacity loop 要倒著走。

from typing import List

def subset_sum(nums: List[int], target: int) -> bool:
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

倒著走可以避免同一輪重複使用目前 item。

Unbounded Knapsack
#

每個 item 可以重複使用，所以 capacity loop 通常往前走。

from typing import List

def coin_change_min(coins: List[int], amount: int) -> int:
    inf = amount + 1
    dp = [inf] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)

    return -1 if dp[amount] == inf else dp[amount]

Counting Combinations vs Permutations
#

如果要數 combinations，items 放外層：

for coin in coins:
    for amount forward:
        dp[amount] += dp[amount - coin]

如果要數 ordered sequences，target 放外層：

for total in range(target + 1):
    for num in nums:
        dp[total] += dp[total - num]

這就是 LC 518 和 LC 377 最重要的差別。

Grouped / Bounded Knapsack（分組背包）
#

每一組最多選一個選項（同一題目選幾題、同一堆拿幾個、同一個數變成哪個值）。容量一樣要倒著走，在裡面枚舉這一組的所有選項：

dp = [0] + [inf] * target               # 或計數：[1] + [0] * target
for group in groups:
    for s in range(target, -1, -1):      # 倒著走：同一組不會被選兩次
        for weight, value in group:      # 這一組的每個選項
            if s - weight >= 0:
                dp[s] = min(dp[s], dp[s - weight] + value)