0/1 背包問題的計算是透過在物品與容量上建立動態規劃表,在每個儲存格保留兩個狀態中較大的值:不納入當前物品的最佳價值,以及在剩餘容量下疊加先前選擇所得到的最佳價值。對於容量 C 與 n 個具有整數重量的物品,該表共有 (n+1) × (C+1) 個儲存格,每個儲存格儲存該前綴與容量下可達到的最大價值。表格填滿後,求解器會沿著所記錄的決策往回走,以重建被選中的標籤。由於每個儲存格都儲存了對較小子問題的已證明最大值,因此最後一列最後一列的儲存格,即可證明為有界 0/1 模型的全域最佳解——這不是近似值,不是啟發式,也不是猜測。同一套動態規劃方法記載於 Google OR-Tools 的背包參考資料,以及 Stanford CS161 的 0/1 背包動態規劃課程筆記。實際應用此計算的一種方式是使用 背包問題計算機,它在本地執行相同的 DP、強制使用整數容量與重量,並精確回報哪些物品被選中以及相關總計。
0/1 計算的精確機制
0/1 背包問題是一個單一容器的選擇問題:給定 n 個物品,每個物品具有正整數重量 w_i 與非負價值 v_i,以及一個容量 C,在 x_i ∈ {0, 1} 的條件下,最大化總價值 Σ v_i · x_i,且需滿足 Σ w_i · x_i ≤ C。每個物品只能被排除或選中一次——它不能被分割、重複,或部分裝入。DP 表在每個儲存格上表達這個成對的約束(物品索引、剩餘容量)。
dp[i][c] 的狀態,是在不超過容量 c 的前提下,使用前 i 個物品所能達到的最大總價值。狀態轉移會比較兩個選擇:跳過物品 i 並保留 dp[i-1][c],或納入物品 i(僅在 w_i ≤ c 時合法),繼承 dp[i-1][c - w_i] 並加上 v_i。較大的值會被儲存,連同產生該值的決策,以便稍後回溯。當 w_i > c 時,唯一合法的選擇是跳過,因此 dp[i][c] 化簡為 dp[i-1][c]。
經過列壓縮後,複雜度為時間 O(n · C)、記憶體 O(C),這也是它在整數小重量下執行最快的緣故。以價值重量比挑選物品的貪婪啟發式,在 DP 能精確處理的情形上會失效。Google OR-Tools 參考資料將相同的目標描述為「在不超過容量的前提下,選擇總價值最大的子集合」,而底層的表格遍歷機制則在 Stanford CS161 的 0/1 DP 課程中詳細說明。
0/1 背包與相鄰模型的比較
在計算之前,請先確認 0/1 背包確實是你需要的模型。兩者在措辭上的差異很小,但在結果上的差異很大。
| 變體 | 容器數量 | 物品使用方式 | 是否允許分割 | 常見求解器 |
|---|---|---|---|---|
| 0/1 背包(本計算機) | 1 | 每項 0 或 1 次 | 否 | 精確 DP |
| 分數背包 | 1 | 任意分數,連續 | 是 | 依比例的貪婪 |
| 多重背包 | 多個,每個皆有限制 | 每個箱子 0 或 1 個 | 否 | 分支界限、ILP |
| 裝箱問題 | 多個等容量箱子 | 每個箱子 0 或 1 個 | 否 | FFD / BFD 啟發式 |
| 無界背包 | 1 | 無限次數 | 否 | 允許重量重複的 1-D DP |
若你的問題涉及兩個或以上的容器、可重複的物品,或物品的分數,本計算機將無法精確建模。針對多容器情況,裝箱問題計算機會以確定性的首次適配遞減方式,將標記過的尺寸裝入等容量箱子,這是相關但不同的目標。
如何逐步計算背包問題
- 開啟背包問題計算機,在容量欄位中輸入 1 到 10,000 之間的一個整數容量。
- 使用「標籤、重量、價值」的格式,將每個物品新增為一行。重量必須為正整數;價值可為零或正小數。請勿在標籤內使用逗號,因為逗號會用於分隔三個欄位。
- 當所有候選項目都列完後,即可停止新增。本工具最多接受 100 個具有唯一標籤的物品,並會依標籤拒絕重複項目。
- 點擊「求解」。計算機會驗證輸入、在瀏覽器中建立 DP 表,並回溯所選的物品。被選中的標籤、總價值、總重量與剩餘容量會顯示於結果面板中。
- 在複製選取結果之前,請逐項檢查並確認所列的假設。複製按鈕會將純文字放入剪貼簿,以便用於筆記或試算表。
若你的輸入包含固定小數的量測值——例如 2.5 公斤——請在輸入前統一乘以 10(或 100),使重量保持為整數。較細的刻度會產生較大的表格,這也是本計算機將容量上限設為 10,000、物品清單上限設為 100 行的原因。任何特定情境的精確數字,應透過將該輸入實際帶入計算機計算,而非以手動方式算出。
範例演練:容量為 10 的案例
為了實際觀察計算過程,取容量 C = 10 以及三個候選物品:Crystal(重量 4、價值 40)、Module(重量 3、價值 50),以及 Heavy(重量 9、價值 89)。
步驟 1——第 0 列為空前綴:dp[0][w] = 0,適用於所有容量 0..10。
步驟 2——第 1 列(Crystal, 4/40)。在 w = 10 時,dp[1][10] = max(dp[0][10] = 0, 40 + dp[0][6] = 40) = 40,因此表格記錄「納入 Crystal」。
步驟 3——第 2 列(Module, 3/50)。在 w = 10 時,dp[2][10] = max(dp[1][10] = 40, 50 + dp[1][7] = 50 + 40 = 90) = 90,因此納入 Module,而回溯會回到 dp[1][7],其本身為「納入 Crystal」。
步驟 4——第 3 列(Heavy, 9/89)。在 w = 10 時,dp[3][10] = max(dp[2][10] = 90, 89 + dp[2][1] = 89 + 0 = 89) = 90。Heavy 被排除,並保留先前的最佳解。
最終狀態:dp[3][10] = 90,總重量為 4 + 3 = 7,剩餘 3 個單位的未用容量。單獨選擇 Heavy 的天真貪婪做法,在重量 9 時只會得到 89。DP 透過考慮所有配對,而不是依比例排序,找到了嚴格更佳的解。
| 策略 | 選中的標籤 | 總價值 | 總重量 | 是否為已證明最佳解? |
|---|---|---|---|---|
| 貪貪:優先選擇能裝下的最大物品 | Heavy | 89 | 10 之 9 | 否——錯失了更佳的配對 |
| 貪貪:優先選擇最高價值重量比 | Module + Crystal | 90 | 10 之 7 | 巧合——無法證明 |
| 精確 0/1 動態規劃 | Module + Crystal | 90 | 10 之 7 | 是——已證明最大值 |
此輸入正是背包問題計算機隨附的八個黃金測試案例之一,目的是確認求解器在具誤導性的輸入順序下,絕對不會退而採用最高價值重量比的啟發式。
如何解讀計算機的輸出
一旦背包問題計算機完成計算,四個數字即可說明整個結果:被選中的物品清單、總價值(DP 已證明為最大的數字)、總重量(恆 ≤ 容量——測試套件會對此進行斷言),以及剩餘容量。依序閱讀這些數字,可避免大多數的誤用。
若兩個不同的子集合具有相同的最大價值,本工具會保留較早出現的解,而不是任意切換——也就是 DP 為該平局所記錄的第一組標籤。對相同的輸入重複執行時,這種確定性讓你能一次修改一行,並比對輸出差異,以便比較各種情境。
一個常見的誤讀是將結果視為實體裝箱計畫。表格中沒有形狀、平衡或易碎性的概念,因此一個「完美」的價值最大化選擇,在實體容器中仍可能放不下。請將輸出視為在單一純量成本下的價值最大化選擇,並另行納入實體上的限制條件。
計算機強制執行的限制——以及刻意忽略的事項
有幾類輸入會被拒絕而非被默默忽略,以避免答案成為幻影最佳解:空白欄位、重複標籤、標籤內含逗號、格式錯誤的逗號分隔列、非正整數的重量、非有限值(如 NaN 或缺失文字),以及重量大於所輸入的容量。重量超過容量的物品會以驗證錯誤的形式回傳,而不是被默默捨棄,這能明確顯示在目前容量下,該輸入無法表示為可選的候選項目。
同樣重要的是這個模型「不知道」什麼。DP 不會建模實體尺寸、平衡性、易碎性、物品之間的交互、強制群組、不相容的配對、截止期限或不確定性。八個經人工審核的測試案例會驗證:被選中的重量絕不會超過容量,且完全裝滿、等值平局、小數值與零價值物品都能正確處理。
對於高風險用途——金融投資組合、安全裝載計畫、醫療資源分配——純量 0/1 模型雖屬必要,但並不充分;在套用選擇之前,目標函數、物品之間的相依性,以及現實世界的後果,仍須由適當的領域模型與可問責的審查者進行驗證。
延伸閱讀:以匈牙利法求解指派問題。