背包問題總結

一、什么是背包問題？

定義：給定一個容量為 W 的背包和 n 件物品，每件物品有一個重量 w[i] 和價值 v[i]，要求選擇若干物品放入背包，在不超過容量的前提下，使總價值最大。

背包問題本質是：約束優化 + 組合選擇。

---

二、什么時候考慮用“背包思想”？

你可以在如下類型的問題中嘗試用背包建模：

題目特征	關鍵詞	是否適合背包建模？
有一個資源上限（如時間、錢、容量）	“最多”、“不超過”、“限制在…”	資源即背包容量
有多個選項可選，每個選項有代價和收益	“每個選擇有花費和收益”、“從中選擇一些”	每個選項就是一個“物品”
要最大化或最小化一個目標值（如最大收益、最小時間）	“求最大值/最小值”、“最優”	屬于優化問題
每個選項只能選一次/多次/無限次	“可重復選”/“不可重復”	可映射到 0-1、完全、多重背包
組合問題，多個變量之間的選擇組合	“在多個物品中挑選”	用狀態轉移建模組合方式

一句話記憶：
多個物品（選項），有一個資源限制，要做出最優組合決策，就可以考慮“背包思想”。

---

三、常見背包模型（及其差異）

類型	是否可重復	限制條件	應用舉例
0-1 背包	否	每個物品最多選一次	挑戰任務只能做一次
完全背包	是（無限）	每個物品可選任意次	硬幣兌換、無限庫存商品
多重背包	是（有限）	每個物品最多選 k 次	有限庫存下的選購問題
分組背包	分組內最多選一個	每組內只能選一個	每種類別選一個代表
混合背包	混合限制	混合以上任意模型	綜合現實場景，如同時有限和無限物品
二維/多維背包	多維限制	除重量外還有其他限制	同時限制時間/金錢等多種資源

---

四、狀態表示 & 轉移方程

通用思路

• 狀態定義：dp[i][j] 表示前 i 個物品中，容量為 j 時可獲得的最大價值。

• 狀態轉移：

  • 不選第 i 個物品：dp[i][j] = dp[i-1][j]
  • 選第 i 個物品：dp[i][j] = dp[i-1][j - w[i]] + v[i]（要滿足 j >= w[i]）

狀態壓縮（降維優化）

因為 dp[i][*] 只依賴于 dp[i-1][*]，所以可以使用一維數組。

各類背包的一維優化寫法對比：

類型	j 遍歷順序	解釋
0-1 背包	for j from W down to w[i]	倒序：防止多次選擇同一物品
完全背包	for j from w[i] to W	正序：允許重復使用當前物品
多重背包（二進制拆分）	拆成若干個 0-1 物品后處理	防止超時

---

五、例題歸類（每種類型都附帶一個經典應用）

背包類型	題目示例	描述
0-1 背包	經典最大價值問題	n 件物品，每個選一次，背包容量為 W
完全背包	硬幣兌換	無限數量的硬幣組成目標金額
多重背包	商品選購	每種商品有庫存限制
分組背包	項目選擇	每類項目只能選一個，例如 CPU/顯卡/內存 各選一個
混合背包	商店打折組合	有些商品有限，有些無限
二維背包	同時限制金錢和時間	如同時給出“時間限制”和“重量限制”

---

六、注意事項 & 常見錯誤

問題	錯誤描述	正確做法
遍歷順序寫錯	完全背包使用倒序	完全背包需正序遍歷 j
狀態轉移寫錯	忘了判斷 j >= w[i]	加上條件判斷
多重背包暴力寫法超時	三重循環	用二進制拆分優化
使用二維數組時初始化錯	未初始化第 0 行	初始化 dp[0][*] 為 0

---

七、總結口訣

背包問題口訣：

多個物品選幾個，容量限制是核心；
選或不選看約束，價值最大找最優；
可重復用正序掃，只能選一次就倒流；
多重拆成 0-1 背，分組記得內部分組選。