在 0/1 背包問題中，xi 是一個二元決策變數，當物品 i 被裝入時等於 1，當物品 i 被排除時等於 0，目標是在不超過容器容量上限的前提下，找到能讓總價值最大的 xi 值。標準的數學規劃會將目標函數寫成 vi·xi 對 i 的總和，限制式則要求 wi·xi 對 i 的總和必須小於或等於 C，也就是單一容器的容量。由於每個物品都不可分割，每個 xi 只能是 0 或 1 — 不可能是 0.5 或 0.7 — 而且同一個物品不能被選取兩次。n 個物品的所有 xi 值所構成的集合就是解答向量 X = (x1, x2, …, xn)，找出 X 就等同於指明最佳子集。你可以建立一張以物品和容量為索引的動態規劃表，然後回溯所記錄的決策，讀出哪些 xi 被設為 1。背包問題計算機 會自動執行這個程序，並回傳每個被選取標籤的總價值、總重量以及未使用的容量。
Xi 在 0/1 背包問題中所代表的意義
每個 xi 都是一個二元開關，用來控制物品 i 是否進入背包。當你寫出解答時，向量 X = (x1, x2, …, xn) 中的每個變數只能是 0 或 1，絕對不會是分數。值為 0 代表物品 i 不放進容器;值為 1 代表物品 i 整個被取走。xi 不能取其他值的這個限制，正是這個問題被稱為「0/1」版本而非分數版本的原因。
一旦你讀出 xi 的值，就能立刻知道子集:把所有 xi = 1 的索引 i 納入，並把所有 xi = 0 的索引 i 排除。子集和 X 向量是描述同一個答案的兩種方式。背包問題計算機以被選取標籤的清單形式呈現答案，而清單中的每個標籤，都對應到底層解答中 xi 值為 1 的變數。
| Xi 值 | 意義 | 對總重量的影響 | 對總價值的影響 |
|---|---|---|---|
| 0 | 物品 i 被排除 | wi 不被計入 | vi 不被計入 |
| 1 | 物品 i 整個被選取 | wi 被加入一次 | vi 被加入一次 |
以決策變數表示的數學規劃
標準的整數規劃會把 xi 當作決策變數，wi 是物品 i 為正的整數重量，vi 是其非負的價值，C 則是單一的整數容量。模型如下:
最大化 Σ(i=1 到 n) vi·xi 限制式 Σ(i=1 到 n) wi·xi ≤ C xi ∈ {0, 1} 對每個 i
這個規劃正是 Google OR-Tools 所描述的:在容量限制內，挑選總價值最大的子集 (Google OR-Tools — 背包問題)。這是典型的單一容器 0/1 模型，也是背包問題計算機所求解的精確模型。
| 變體 | 決策變數範圍 | 物品可以被分割嗎? | 容器數量 |
|---|---|---|---|
| 0/1 背包 | xi ∈ {0, 1} | 不行 — 整個取走或完全不放 | 一個 |
| 分數背包 | xi ∈ [0, 1] | 可以 — 允許任意比例 | 一個 |
| 多重背包 / 裝箱問題 | xi ∈ {0, 1} | 不行 — 整個取走或完全不放 | 多個相同的容器 |
這三個問題看起來很相似，但其實問的是不同的事情。只有 0/1 那一列符合計算機所回傳的結果。如果你的實際情境允許分割物品，或者你擁有的容器不只一個，那麼這個工具所回報的 xi 值就不是你需要的答案。
利用動態規劃遞迴求出 Xi
對於具有整數重量的單一容量 0/1 問題，找出每個 xi 的精確方法是對一張二維表格進行動態規劃。令 DP[i][c] 為僅使用前 i 個物品且容量為 c 時可達到的最大總價值。對於表格中的每個儲存格，遞迴會比較兩種情況:
DP[i][c] = max(DP[i−1][c], DP[i−1][c − wi] + vi)
第一項代表排除物品 i(因此 xi = 0)。第二項代表納入物品 i(因此 xi = 1)，它會把 vi 加上前 i − 1 個物品在容量 c − wi 下的最佳值。兩者中較大的那個會被保留。這個遞迴是 0/1 問題的標準處理方式(請參考 Stanford CS161 — 0/1 背包動態規劃)。
在 i = 1 … n 以及 c = 0 … C 填滿整張表格後，你可以從 DP[n][C] 往回走來還原 xi 的值。在第 i 步且剩餘容量為 c 時，比較 DP[i][c] 與 DP[i−1][c]。如果兩者相等，代表物品 i 被排除，xi = 0，且 c 保持不變。如果 DP[i][c] 嚴格較大，代表物品 i 被納入，xi = 1，然後你在移到物品 i − 1 之前，要把 c 減去 wi。這次回溯只要一趟就能產生完整的解答向量 X。
有一個細節在兩個儲存格平手時很重要:價值相等的平手情況會保留較早的解，而不是任意切換，所以相同的輸入總是會產生相同的 xi 值。這種確定性正是計算機輸出在多次執行間能保持一致的原因。
如何使用背包問題計算機找出 Xi
- 在容量欄位中輸入介於 1 到 10,000 之間的整數容量。所有物品請使用相同的重量單位 — 例如全部使用公斤或全部使用公克。
- 按照標籤、重量、價值的順序，將每個不可分割的物品新增為一列，並使用正的整數重量。如果你的測量值帶有固定小數位，請在輸入前一致地進行縮放(例如，把 2.5 公斤轉成 25 個十分位)，並記得細一點的刻度會產生更大的表格。
- 確認沒有兩列使用相同的標籤，因為重複的標籤會被拒絕;也要確認沒有任何重量超過你所輸入的容量 — 重量超過容量的物品會被拒絕，而不是被默默忽略。
- 求解精確的 0/1 模型。計算機會建立以物品和容量為索引的標準動態規劃表，在價值平手時保留排除的解，並回溯出最大值的選擇。
- 檢查結果中每個被選取的物品和假設。輸出會指出每個被選取的標籤、總價值、總重量以及未使用的容量。輸出中出現的每個標籤，都對應到 xi = 1;輸出中未出現的每個標籤，則對應到 xi = 0。
- 如果需要把子集或總計貼到報告、試算表或作業解答中，請以純文字格式複製選取結果。
範例演練:為一個四個物品的問題找出 Xi
考慮四個具有整數重量和價值的物品，以及容量為 10 的容器。
- 物品 A:重量 4，價值 40
- 物品 B:重量 3，價值 50
- 物品 C:重量 5，價值 60
- 物品 D:重量 2，價值 30
DP 遞迴會比較納入和排除每個物品的情況。在單獨處理完物品 A 之後，容量 10 時的最佳價值是 40(取 A:重量 4 ≤ 10，價值 40)。對於容量 10 的物品 B，納入 B 會用掉 3 個單位，並結合 {A} 在容量 7 時的最佳值 40，得到 40 + 50 = 90。排除 B 則讓 DP 維持 40，所以表格保留 90。繼續處理物品 C 和 D，容量 10 時可達到的最大值是 140，由物品 B、C 和 D 一起選取達成:重量 3 + 5 + 2 = 10，價值 50 + 60 + 30 = 140。
從這個最佳解讀出 xi 值，可得到解答向量 X = (0, 1, 1, 1)，也就是 xA = 0、xB = 1、xC = 1、xD = 1。總重量為 10，等於容量，且 10 − 10 = 0 個單位的容量未被使用。背包問題計算機在相同輸入下會重現這個精確的結果。
純量模型的限制，以及單靠 Xi 不足的情境
計算機所回傳的 xi 值，只有在所述的 0/1 模型之內才具有數學上的最佳性:單一容量、整數重量、非負的價值，且每個物品只能使用一次。這個工具刻意不對實體尺寸、平衡性、易碎性、物品之間的交互作用、強制群組、不相容的配對、期限、風險或不確定性進行建模，因此即使在純量上最佳的選擇，仍然可能在實體上不可行，或在運作上不合適。
容量和重量必須是整數，因為動態規劃表格的每個容量單位都有一個狀態。清單最多容納 100 個唯一標籤，容量上限為 10,000，以確保瀏覽器的記憶體和回應時間受到控制。價值可以是零或正的小數，不需要與重量的單位相同。空白欄位、重複的標籤、非正的重量、大於容量的重量、非有限的數值，以及格式錯誤的逗號分隔列，都會被拒絕，而不是被默默修正。
此結果適用於課堂習題、在明確努力預算下的功能優先排序、有界投資組合的例子，或小規模的配置草稿。對於財務投資組合、安全負載、醫療資源分配，或其他高風險的決策，純量的 0/1 模型並不足夠 — 在依據 xi 值採取行動之前，請使用合適的領域模型與負責任的審核者，來驗證目標、相依性、限制條件以及真實世界的後果。
想進一步了解，請參考 如何在 Excel 中求解指派問題。