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