Algorithm - DP Knapsack

想參考 DP 背包問題的各種實戰題型的話，我有整理底家，直接開打 XD：

LeetCode - 0/1 Knapsack Problems LeetCode - Complete Knapsack Problems LeetCode - Multiple Knapsack Problems

DP Knapsack Note

背包其實就三種你要會分：

類型	特徵
0/1 背包	每個物品只能用一次
完全背包	每個物品可以用無限次（Coin Change）
多重背包	每個物品有數量限制

背包問題的本質不是「選物品」，而是：在容量限制下，做選擇，並且把問題拆成子問題

幾乎所有背包題都可以轉換成：

dp[j] = 在容量 j 下，可以得到的最佳結果

背包問題的核心只有兩件事：

1. 這個物品要不要選？
2. 這個物品能不能重複選？

0/1 背包 (每個物品只能使用一次)

適用於：

• 每個物品只能使用一次
• subset / partition 類問題
• 選或不選某個元素

for (int i = 0; i < n; ++i) {
    for (int j = capacity; j >= weight[i]; --j) {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

特性

• j 從大到小
• 避免同一個物品在同一輪被使用多次
• 核心是「選或不選」

不選第 i 個物品：dp[j]
選第 i 個物品：dp[j - weight[i]] + value[i]

所以轉移是：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

為什麼 0/1 背包要倒著跑？

因為每個物品只能用一次。

假設正著跑：

for (int j = weight[i]; j <= capacity; ++j)

那 dp[j] 可能會用到這一輪剛更新過的 dp[j - weight[i]]，這樣就等於同一個物品被重複使用了。

所以 0/1 背包必須倒著跑：

for (int j = capacity; j >= weight[i]; --j)

這樣才能確保 dp[j - weight[i]] 還是上一輪的狀態，也就是還沒使用第 i 個物品以前的結果。

value[i] 要加什麼？

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

關鍵：

+什麼 = 你想最大化的東西
dp 存什麼 → 就加什麼

例子：

最大數量（474） → +1
最大總和（1049） → +weight[i]
最大價值（一般背包） → +value[i]

完全背包 (每個物品可以使用無限次)

適用於：

• 每個物品可以使用無限次
• coin change 類問題
• 題目明確說可以重複使用

for (int i = 0; i < n; ++i) {
    for (int j = weight[i]; j <= capacity; ++j) {
        dp[j] = min(dp[j], dp[j - weight[i]] + value[i]);
    }
}

特性

• j 從小到大
• 允許同一個物品被重複使用
• 會用到這一輪已經更新過的 dp[j - weight[i]]

為什麼完全背包要正著跑？

因為每個物品可以用無限次。

正著跑時：

for (int j = weight[i]; j <= capacity; ++j)

dp[j] 可以用到同一輪剛更新過的 dp[j - weight[i]]。

這代表：

我可以再拿一次同樣的物品

所以完全背包要正著跑。

從 amount 角度寫完全背包

有些題目也可以從金額或容量角度思考。

以 Coin Change 為例：

dp[j] = 湊出金額 j 所需要的最少硬幣數

可以想成：

最後一枚硬幣是什麼？

模板：

for (int j = 1; j <= amount; ++j) {
    for (int coin : coins) {
        if (j >= coin) {
            dp[j] = min(dp[j], dp[j - coin] + 1);
        }
    }
}

這種寫法很直覺，因為它是從小金額一路推到大金額。

多重背包 (每個物品有使用次數限制)

適用於：

• 每個物品有使用次數限制
• 例如某個物品最多只能用 k 次

最直覺的想法是：

第 i 個物品可以選 0 次、1 次、2 次、...、k 次

但直接枚舉次數可能會太慢。

常見做法是把多重背包轉成 0/1 背包。

例如某個物品有 13 個：

13 = 1 + 2 + 4 + 6

所以可以拆成：

1 個的物品
2 個的物品
4 個的物品
6 個的物品

每一組都只能選一次，這樣就變成 0/1 背包。

如何判斷是哪一種背包

解題時先問：

1. 每個物品可以用幾次？
2. dp[j] 代表什麼？
3. 題目要最大值、最小值，還是方法數？

Step 1：判斷物品能不能重複使用

只能用一次      → 0/1 背包
可以無限次使用  → 完全背包
有固定使用次數  → 多重背包

Step 2：判斷 dp 的意義

常見有三種：

最大價值 → max
最少數量 → min
幾種方法 → +

例如：

Coin Change:
dp[j] = 湊出金額 j 的最少硬幣數

所以是：

min

Coin Change II:
dp[j] = 湊出金額 j 的方法數

所以是：

+

Partition Equal Subset Sum:
dp[j] = 是否能湊出總和 j

所以是：

boolean

Step 3：判斷 j 的方向

類型	物品能不能重複用	j 的方向
0/1 背包	不能	由大到小
完全背包	可以	由小到大
多重背包	有限制	拆成 0/1 背包

判斷更新方式的核心原則

關鍵問題是：

這個物品在同一輪能不能被再次使用？

如果不能重複使用：

for (int j = capacity; j >= weight[i]; --j)

如果可以重複使用：

for (int j = weight[i]; j <= capacity; ++j)

所以背包問題最重要的記憶點是：

0/1 背包：倒著跑，避免重複使用
完全背包：正著跑，允許重複使用

最少數量型背包

例如：

322. Coin Change

題目問：

湊出 amount 最少需要幾個 coin？

dp 定義：

dp[j] = 湊出金額 j 的最少硬幣數

初始化：

vector<int> dp(amount + 1, INF);
dp[0] = 0;

轉移：

dp[j] = min(dp[j], dp[j - coin] + 1);

因為 coin 可以無限次使用，所以是完全背包，j 正著跑：

for (int coin : coins) {
    for (int j = coin; j <= amount; ++j) {
        dp[j] = min(dp[j], dp[j - coin] + 1);
    }
}

如果最後：

dp[amount] == INF

代表湊不出來。

方法數型背包

例如：

518. Coin Change II

題目問：

湊出 amount 有幾種組合？

dp 定義：

dp[j] = 湊出金額 j 的方法數

初始化：

dp[0] = 1;

意思是：

湊出 0 元有 1 種方法：什麼都不選

轉移：

dp[j] += dp[j - coin];

完整模板：

for (int coin : coins) {
    for (int j = coin; j <= amount; ++j) {
        dp[j] += dp[j - coin];
    }
}

這裡外層先枚舉 coin，內層再枚舉 amount，代表算的是「組合數」，不是「排列數」。

組合數與排列數的差別

這是背包題裡很容易混淆的地方。

如果題目問組合數：

1 + 2
2 + 1

算同一種。

通常寫法是：

for (int coin : coins) {
    for (int j = coin; j <= amount; ++j) {
        dp[j] += dp[j - coin];
    }
}

如果題目問排列數：

1 + 2
2 + 1

算不同種。

通常寫法是：

for (int j = 1; j <= amount; ++j) {
    for (int coin : coins) {
        if (j >= coin) {
            dp[j] += dp[j - coin];
        }
    }
}

所以要記得：

先物品再容量 → 組合
先容量再物品 → 排列

Boolean 型背包

例如：

416. Partition Equal Subset Sum

題目問：

能不能從陣列中選一些數字，使總和等於 target？

dp 定義：

dp[j] = 是否能湊出總和 j

初始化：

dp[0] = true;

轉移：

dp[j] = dp[j] || dp[j - num];

因為每個數字只能用一次，所以是 0/1 背包，j 倒著跑：

for (int num : nums) {
    for (int j = target; j >= num; --j) {
        dp[j] = dp[j] || dp[j - num];
    }
}

常見對應關係

題型	背包類型	dp 意義	操作
322. Coin Change	完全背包	最少硬幣數	min
518. Coin Change II	完全背包	組合數	+
416. Partition Equal Subset Sum	0/1 背包	是否能湊出 target	boolean
494. Target Sum	0/1 背包	方法數	+
279. Perfect Squares	完全背包	最少平方數數量	min
377. Combination Sum IV	完全背包變形	排列數	+

經典題目

類型	題目	備註
0/1 背包	416. Partition Equal Subset Sum	每個數字只能選一次，判斷是否能湊出 sum / 2
0/1 背包	494. Target Sum	每個數字只能用一次，轉成「有多少種方法湊出某個 target」
0/1 背包	474. Ones and Zeroes	每個字串只能選一次，限制有兩個容量：0 的數量與 1 的數量
0/1 背包	1049. Last Stone Weight II	每個石頭只能選一次，目標是讓兩堆重量差最小
0/1 背包	2915. Length of the Longest Subsequence That Sums to Target	每個元素只能選一次，求湊出 target 的最長 subsequence
0/1 背包	2787. Ways to Express an Integer as Sum of Powers	每個數字的 power 最多只能用一次，求湊出 n 的方法數
完全背包	139. Word Break	wordDict 裡的字可以重複使用，判斷字串是否能被組成
完全背包	322. Coin Change	每種 coin 可以無限次使用，求最少硬幣數
完全背包	518. Coin Change II	每種 coin 可以無限次使用，求組合數
完全背包	279. Perfect Squares	每個 perfect square 可以無限次使用，求最少數量
完全背包	377. Combination Sum IV	每個數字可以重複使用，且順序不同算不同方法，屬於排列型完全背包
多重背包 / 變形背包	1155. Number of Dice Rolls With Target Sum	有固定 dice 數，每顆骰子只能選一個面，屬於有限次選擇的變形背包
多重背包 / 變形背包	879. Profitable Schemes	每個 crime 只能選一次，但有兩個限制維度：人數與 profit，屬於 0/1 背包變形

建議記憶方式

優先記兩個模板：

0/1 背包：倒著跑
完全背包：正著跑

然後再根據題目問什麼，決定轉移方式：

最大值 → max
最小值 → min
方法數 → +
可不可行 → boolean

解背包題時，優先做這件事：

Step 1：先判斷物品能不能重複用

只能用一次      → 0/1 背包
可以無限使用    → 完全背包
每個有使用上限  → 多重背包

---

Step 2：看題目在問什麼

最大價值 / 最長長度 → max
最少數量           → min
幾種方法           → +
可不可行           → boolean

---

Step 3：判斷是否有「順序影響」

順序不同算不同 → 排列
順序不同算相同 → 組合

總結

背包問題可以統一成：

dp[j] = 用目前考慮過的物品，湊出容量 j 的最佳結果

核心永遠是：

選或不選
能不能重複選

最後的轉移通常長得像：

dp[j] = better(dp[j], dp[j - weight] + value)

差別只在：

better 是 max / min / + / boolean
j 是正著跑還是倒著跑

背包題最重要的觀念是：

迴圈方向決定同一個物品能不能被重複使用

只要能判斷這一點，大部分背包題就不會亂。