0/1 Knapsack背包問題

01為什麼需要它

看到這些關鍵字就想到它：每個東西選或不選、不能拆開、總重量／預算上限、最大化總價值、湊出剛好等於 target 的和、分成兩堆差最小、容量是不大的整數。

02核心概念

n 個物品各自選或不選，組合有 2ⁿ 種，n = 40 就要列舉一兆次。貪婪也不行：互動示範裡 D 的價值重量比 7/5 = 1.4 最高，先拿 D 後只剩 2 的空間，只能再放 A，總價值 8；最佳解卻是比值較低的 B + C = 9。物品不能拆開，比值高的物品可能卡住空間，這是 0/1 背包和可以切一部分的分數背包（按比值貪婪就對）的根本差別。DP 的做法是定義狀態 dp[i][w] = 只考慮前 i 個物品、容量為 w 時的最大價值，然後對第 i 個物品只問一個問題：選還是不選。

轉移式是 dp[i][w] = max(dp[i−1][w], dp[i−1][w−wᵢ] + vᵢ)，第二項只在 w ≥ wᵢ 時存在。為什麼對：看 (i, w) 的任一個最佳解，它要嘛不含物品 i，那它就是前 i−1 個物品在容量 w 下的解，而且必須是最佳的，否則換成更好的那組，(i, w) 也會變好，矛盾；要嘛含物品 i，拿掉 i 之後剩下的必定是前 i−1 個物品在容量 w−wᵢ 下的最佳解，理由相同。這就是最佳子結構。每個子集都落在這兩種情況之一，所以取 max 等於比較了全部 2ⁿ 種組合，卻只需要 (n+1)(W+1) 個不同的子問題。表只記最大價值；要知道選了誰，從 dp[n][W] 往回走，dp[i][w] ≠ dp[i−1][w] 代表這格非選物品 i 不可，記下它、容量扣掉 wᵢ，繼續往上一列。

表有 (n+1)(W+1) 格，每格 O(1)，時間 O(nW)，不論輸入如何都要填滿整張表。二維表的空間也是 O(nW)，但第 i 列只讀第 i−1 列，所以只留一個長度 W+1 的陣列，並讓 w 從 W 倒著掃到 wᵢ：dp[w] = max(dp[w], dp[w−wᵢ] + vᵢ)。倒序時 dp[w−wᵢ] 在這一輪還沒被改寫，讀到的仍是上一列的值，空間降到 O(W)，代價是無法再回溯出選了哪些。要注意 O(nW) 是偽多項式：W 是輸入裡的一個數值，不是輸入的長度，W 多一位數表就大十倍，容量到 10⁹ 時這個方法完全不能用。那時如果價值總和不大，可以交換兩個維度，改成 dp[v] = 湊出總價值 v 的最小重量。

最常見的錯是一維陣列用正序掃 w：dp[w−wᵢ] 已經是這一輪更新過、含有物品 i 的值，同一個物品就被放了好幾次，演算法悄悄變成下一課的完全背包。第二個是初始化：問「容量不超過 W 的最大價值」時全部初始化為 0；問「剛好裝滿 W」時只有 dp[0] = 0，其餘設成 −∞ 表示湊不出來。同一張表換掉合併方式就是其他題型：max 換成 or 是「能不能湊出和 s」的子集和問題，換成加法並令 dp[0] = 1 是「有幾種選法」。和 1-D DP 的 House Robber 相比，背包的狀態多了「剩餘容量」這一維，這是描述有限資源時最常用的狀態設計。

03演算法步驟

1. 1確認題型：每個物品最多選一次、有一個整數容量 W、目標是最大化總價值（或判斷湊不湊得出、數有幾種選法）。物品可以無限次選就是完全背包。
2. 2定義 dp[i][w] = 前 i 個物品、容量 w 時的最大價值。base case：第 0 列全是 0（要求剛好裝滿時只有 dp[0][0] = 0，其餘 −∞）。
3. 3外層 i 從 1 到 n，內層 w 從 0 到 W：先令 dp[i][w] = dp[i−1][w]（不選）；若 w ≥ wᵢ，再和 dp[i−1][w−wᵢ] + vᵢ（選）取大的。
4. 4答案是 dp[n][W]。要列出選了哪些，從 (n, W) 往上走：dp[i][w] ≠ dp[i−1][w] 就記下物品 i 並令 w −= wᵢ，否則 w 不變，直到第 0 列。
5. 5只需要最大價值時做空間壓縮：一維 dp 長度 W+1，外層物品，內層 w 從 W 倒序到 wᵢ，dp[w] = max(dp[w], dp[w−wᵢ] + vᵢ)。
6. 6換題型只改合併方式和初始化：可行性用 or 且 can[0] = True，計數用加法且 ways[0] = 1，迴圈結構完全不變。

04互動示範

四個物品 A（重 1、值 1）、B（重 3、值 4）、C（重 4、值 5）、D（重 5、值 7），容量 7。一格一格填 dp[i][w]：藍色是正在填的格子，黃色是「不選」的來源 dp[i−1][w]，綠色是「選」的來源 dp[i−1][w−wᵢ]。填完後從右下角往上回溯，綠色路徑標出走過的格子，物品列裡綠色是選了、刪除線是沒選。留意最後一格 dp[4][7]：比值最高的 D 選了只有 8，不選反而保住 B + C = 9。

05程式碼

三個函式：二維表加回溯（能列出選了哪些物品）、一維倒序的空間壓縮版（只要最大價值時的標準寫法），以及「分成兩堆差最小」的布林背包。二維版好理解也能回溯，一維版是實際寫題時最常用的。C++ 的布林背包用 std::bitset，can |= can << x 一行就完成一整輪掃描，而且一次處理 64 個位元。

def knapsack_table(weights, values, cap):
    """二維表：dp[i][w] = 只考慮前 i 個物品、容量 w 時的最大價值。O(nW)"""
    n = len(weights)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]   # 第 0 列：沒有物品，全是 0
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(cap + 1):
            dp[i][w] = dp[i - 1][w]                  # 不選第 i 個
            if w >= wt:                              # 放得下才考慮選
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)

    # 回溯：和上一列不同，代表第 i 個物品被選了
    chosen, w = [], cap
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            chosen.append(i - 1)
            w -= weights[i - 1]
    return dp[n][cap], chosen[::-1]


def knapsack(weights, values, cap):
    """空間壓縮：只留一列。O(W) 空間"""
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):
        for w in range(cap, wt - 1, -1):             # 倒序：dp[w - wt] 還是上一列的值
            dp[w] = max(dp[w], dp[w - wt] + val)     # 正序會重複選同一個物品
    return dp[cap]


def min_split_diff(nums):
    """分成兩堆使總和差最小：布林背包，重量就是價值，容量是總和的一半"""
    total = sum(nums)
    half = total // 2
    can = [True] + [False] * half                    # can[s]：挑一些數能不能剛好湊出 s
    for x in nums:
        for s in range(half, x - 1, -1):             # 同樣倒序，每個數只用一次
            can[s] = can[s] or can[s - x]
    best = max(s for s in range(half + 1) if can[s])
    return total - 2 * best                          # 一堆 best，另一堆 total - best


if __name__ == "__main__":
    weights, values = [1, 3, 4, 5], [1, 4, 5, 7]     # A、B、C、D，和互動示範相同
    print(knapsack_table(weights, values, 7))  # (9, [1, 2])：選 B、C
    print(knapsack(weights, values, 7))        # 9
    print(min_split_diff([2, 7, 4, 1, 8, 1]))  # 1（11 對 12）
    print(min_split_diff([1, 5, 11, 5]))       # 0（剛好等分）

06練習題

• LeetCode 416Partition Equal Subset Sum（布林背包，容量是總和一半）Medium
• LeetCode 1049Last Stone Weight II（其實是分兩堆差最小）Medium
• LeetCode 494Target Sum（轉成子集和計數）Medium
• LeetCode 2915Length of the Longest Subsequence That Sums to Target（剛好裝滿，初始化 −∞）Medium
• LeetCode 474Ones and Zeroes（兩種容量的背包）Medium
• LeetCode 879Profitable Schemes（計數加上利潤下限）Hard