Unbounded Knapsack完全背包

01為什麼需要它

看到這些關鍵字就想到它：每種物品無限供應、可以重複選、湊出某個總額、最少個數、最多價值、有幾種組合、找零、切割、Coin Change。

02核心概念

0/1 背包每個物品只有選或不選；完全背包每種物品可以拿任意多件。最直接的想法是對每種物品列舉拿幾件：dp[i][w] = max(dp[i−1][w − k·wᵢ] + k·vᵢ)，k 從 0 到 ⌊w / wᵢ⌋，多了一層迴圈。關鍵觀察是「拿 k 件」等於「先拿 k−1 件，再拿一件」，而拿完一件之後第 i 種物品還能繼續拿，所以轉移式可以寫成 dp[i][w] = max(dp[i−1][w], dp[i][w−wᵢ] + vᵢ)。和 0/1 背包比，唯一的差別是「拿」那一項用的是 dp[i] 而不是 dp[i−1]。

壓成一維陣列時，這個差別就變成內層迴圈的方向。外層跑物品、內層 w 由小到大：算 dp[w] 時，dp[w−wᵢ] 在這一輪已經更新過，代表的正是 dp[i][w−wᵢ]，裡面可能已經放了物品 i，再加一件就是重複使用。為什麼正確：對 w 做歸納，容量 w 的最佳解要嘛完全不用物品 i（就是這一輪還沒改之前的舊值），要嘛至少用一件；拿掉其中一件，剩下的一定是容量 w−wᵢ 在同樣物品下的最佳解，而那一格比 w 小，已經算好了。0/1 背包倒序掃，是為了讓 dp[w−wᵢ] 保持上一輪的舊值，避免同一件被拿兩次。

複雜度：n 種物品、容量 W，每種物品掃一遍 W，時間 O(nW)，一維陣列空間 O(W)，沒有好壞情況之分。求最少個數、求方法數只換掉轉移裡的運算，複雜度不變。要注意這是偽多項式：時間跟 W 的數值成正比，不是跟輸入的位元數成正比，W 是 10⁹ 時連陣列都開不出來。要還原選了哪些物品，多開一個 O(W) 陣列記下每一格是由哪個物品轉移來的。

三個常見錯誤。第一是初值：容量「不超過 W」求最大價值，全部設 0；「剛好湊滿」求最少個數，dp[0] = 0、其餘設 ∞，否則湊不出來的金額會被當成 0；求方法數則 dp[0] = 1。第二是計數時的迴圈順序：外層物品、內層金額算的是組合數（LeetCode 518），因為每種物品只在自己那一輪被考慮，順序被固定了；外層金額、內層物品算的是排列數（LeetCode 377）。求最大值或最小值時兩種順序答案一樣，只有計數會不同。第三是 C++ 的溢位：方法數的中間值可能遠大於最後答案。和 Coin Change (Greedy) 那一課的關係是：貪婪只在標準幣制下正確，完全背包是任何幣值都對的一般解；每種物品有數量上限的多重背包，則把數量拆成 1、2、4、… 件一包加上剩下的零頭，轉回 0/1 背包。

03演算法步驟

1. 1確認題型：每種物品可以重複使用，要湊出或不超過某個總量 W。定義 dp[w] 為總量 w 時的最佳值或方法數。
2. 2依目標設初值：不超過 W 求最大價值，全部 0；剛好湊滿求最少個數，dp[0] = 0、其餘 ∞；求方法數，dp[0] = 1、其餘 0。
3. 3外層跑物品，內層 w 從 wᵢ 由小到大跑到 W：最大價值用 dp[w] = max(dp[w], dp[w−wᵢ] + vᵢ)，最少個數用 min(dp[w], dp[w−wᵢ] + 1)，方法數用 dp[w] += dp[w−wᵢ]。
4. 4若題目要的是排列數（順序不同算不同），把兩層對調：外層 w 從 1 到 W，內層跑物品，wᵢ ≤ w 才轉移。
5. 5答案在 dp[W]。剛好湊滿的版本若 dp[W] 仍是 ∞，代表湊不出來，回傳 −1。C++ 計數時改用 unsigned long long。

04互動示範

硬幣 [1, 2, 5]、金額 11，求最少硬幣數。「完全背包（正序）」每種硬幣一輪、金額由小到大掃；「0/1 背包（倒序）」用同一條轉移式，只把金額改成由大到小，等於每種硬幣只有一枚。藍色是正在填的格子，灰色的 ∞ 是還湊不出來的金額，來源格 dp[w−coin] 若是綠色代表還是上一輪的值，黃色代表這一輪剛更新過，也就是同一種硬幣被再用了一次。留意正序模式裡黃色出現的地方，以及兩個模式最後 dp[11] 一個是 3、一個是 ∞。

05程式碼

最大價值的完全背包，加上兩個最常考的變形：最少硬幣數，以及方法數的組合版與排列版。組合與排列放在一起，是為了看清楚兩層迴圈對調之後算的是不同的東西。C++ 的計數版本用 unsigned long long，處理中間值溢位。

# 完全背包：每種物品數量不限。dp[w] = 容量不超過 w 時的最大價值
# 0/1 背包唯一的差別：內層改成 range(cap, wt - 1, -1) 倒序
def unbounded_knapsack(weights, values, cap):
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):       # 外層：物品
        for w in range(wt, cap + 1):           # 內層正序：dp[w - wt] 可能已經拿過這個物品
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]


# 最少硬幣數（LeetCode 322）：要剛好湊滿，湊不出來的金額設成 ∞
def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1


# 組合數（LeetCode 518）：外層硬幣、內層金額，1+2 和 2+1 只算一種
def count_combinations(coins, amount):
    dp = [1] + [0] * amount                    # 湊出 0 元有一種方法：什麼都不拿
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]


# 排列數（LeetCode 377）：內外迴圈對調，1+2 和 2+1 算兩種
def count_permutations(nums, target):
    dp = [1] + [0] * target
    for a in range(1, target + 1):             # 外層：金額
        for x in nums:                         # 內層：最後一步放哪一個
            if x <= a:
                dp[a] += dp[a - x]
    return dp[target]


if __name__ == "__main__":
    # 10 公尺的料，切成 3、4、5 公尺各賣 260、340、420 元
    print(unbounded_knapsack([3, 4, 5], [260, 340, 420], 10))  # 860（3 + 3 + 4）
    print(coin_change([1, 2, 5], 11))          # 3（5 + 5 + 1）
    print(coin_change([7, 10, 25], 63))        # 6（25 + 10 + 7 × 4）
    print(coin_change([5, 10], 3))             # -1
    print(count_combinations([6, 10, 24], 120))  # 16
    print(count_permutations([6, 10, 24], 120))  # 39614

06練習題

• LeetCode 322Coin Change（最少個數，初值設 ∞）Medium
• LeetCode 518Coin Change II（組合數，外層硬幣）Medium
• LeetCode 279Perfect Squares（物品是 1、4、9、…）Medium
• LeetCode 377Combination Sum IV（排列數，迴圈對調）Medium
• LeetCode 139Word Break（字可以重複用，順序有關）Medium
• LeetCode 1449Form Largest Integer With Digits That Add up to Target（剛好湊滿，再比位數）Hard