分數背包問題的解法是將各個物品依「價值對重量比」由高到低排序，然後貪心地盡可能取走能放入的份量，若有需要則最後再取走一小部分物品。這個一句話的規則就是完整的演算法。給定一個容量限制、一份包含物品重量與價值的清單，並允許將物品切割成小塊，把清單排序後，由最高比例往最低比例依序處理，只要整個物品仍放得下就全取，到了下一個物品會超出剩餘容量的情況，則只取恰好能填滿背包的那個比例。因為貪心規則符合類似擬陣的交換性質，而任何剩餘容量都可透過切割單一物品恰好吸收，所以此方法在分數模型下是可證明的最佳解——但僅限於分數模型。一旦物品變得不可分割（即 0/1 背包問題），同一條規則就可能產生比完整動態規劃掃描更差的答案。當你在處理無法切割的物件時，這個區別至關重要。
分數背包問題在問什麼
分數背包問題從一個容量固定為 W 的背包與 n 個物品的清單開始。每個物品 i 有重量 w_i 與價值 v_i。任務是決定每個物品要放入背包多少，使得總重量不超過 W，且總價值盡可能大。與多數實體裝箱問題不同，每個物品的取用比例可以是 0 到 1 之間的任何實數——你可以取整個、不取，或取中間任何比例。
由此產生兩個結果。首先，由於只要還有剩餘空間就一定還能擠進下一個物品的薄片來提高價值，因此答案必定是恰好裝滿背包。其次，分數模型是教科書中貪心演算法可被證明為最佳解的經典案例——這是少數擁有此特性的背包變體之一。Google 的 OR-Tools 背包問題說明文件將其底層目標描述為：在不超出容量的前提下，選擇總價值最大的子集合，這也正是驅動整個家族的標量目標。
逐步解析貪心演算法
分數背包的經典貪心程序執行時間為 O(n log n)，其中排序佔據了主要成本。各步驟如下：
- 計算每個物品的「價值對重量比」v_i / w_i。
- 依該比例由高到低排序；若比例相同，則依輸入順序或任何固定規則排序以保持確定性。
- 走訪排序後的清單。針對每個物品，若整個重量仍可放入剩餘容量中，則完全取走並扣除其重量。
- 若下一個物品會超出剩餘容量，則只取該物品的 remaining_capacity / w_i 比例。這會恰好裝滿背包並結束演算法。
- 加總所有完整物品的價值與最後那個分數部分的價值；其總和即為最佳解。
正確性的論證很簡短：在任何步驟中，保留最高的剩餘比例並盡可能取走該比例的物品，並不會因為跳過它、改取比例較低的物品而獲得改善，因為比例較高的物品每消耗一單位容量所提供的價值至少一樣多。由於模型允許分數，一定能透過切割單一物品來吸收最後的剩餘空間，這正是完成證明的關鍵。
一個分數範例的逐步推演
假設背包容量 W = 50，桌上有三個物品：
| 物品 | 重量 | 價值 | 價值對重量比 |
|---|---|---|---|
| X | 10 | 60 | 6.0 |
| Y | 20 | 100 | 5.0 |
| Z | 30 | 120 | 4.0 |
按比例排序後的順序為 X、Y、Z。完整取走 X：重量 10，剩餘容量 40，累計價值 60。完整取走 Y：再增加 20 重量，剩餘容量 20，累計價值 60 + 100 = 160。Z 需要 30 重量，但只剩 20，因此取 Z 的 20/30 = 2/3 比例。該比例的價值為 (2/3) × 120 = 80。總價值 = 60 + 100 + 80 = 240。總重量 = 10 + 20 + 20 = 50。背包裝滿了，且貪心所得的 240 即為分數模型下的最佳解。
同樣三個物品在 0/1 規則下會迫使不同的選擇：你必須完整取走 Z 或完全不取。取走 Z（重量 30、價值 120）會剩下 20 容量，可完整放入 Y（重量 20、價值 100），合計 220。任何其他組合——X+Y = 160、X+Z = 180——都明顯差於分數模型的 240。這個差距正是分數自由度所帶來的價值。
分數貪心法失效之處
按比例排序的貪心規則僅在允許分數時才是最佳。一旦物品必須整體選擇——進一列、出一列，不可切割、不重複——問題就變成 0/1 背包問題，且同一條規則可能錯過最佳解。Stanford CS161 關於 0/1 背包的課程筆記用一個小型反例說明此觀點：容量為 10，一個重量 6、價值 6 的物品（比例 1.0），以及一個重量 5、價值 9 的物品（比例 1.8）。分數模型的答案是完整取走 5 的物品，再加上 6 的物品之 5/6，合計 9 + 5 = 14。0/1 的答案則必須二擇一：取 5 的物品得 9，取 6 的物品得 6，且任何組合都會超出容量。在更長的清單中，失敗的情況會更為細微——貪心序列可能在結尾留下未用完的容量，而另一個略微不同的組合本可更有效率地運用。
這正是 0/1 問題改用動態規劃來求解的實務原因：只有對每個子集合進行精確搜尋（或等價的動態規劃掃描）才能證明其為最佳解。背包問題計算機針對單一容量、至多 100 個有標籤的物品，以及不大於輸入容量的正整數重量，實作了該精確的動態規劃掃描。
如何使用計算機求解 0/1 版本
- 在容量欄位中輸入 1 到 10,000 之間的整數容量。
- 為每個物品新增單獨一列，內含三個以逗號分隔的欄位：唯一標籤、正整數重量，以及價值（整數或小數，可為零）。
- 再次確認沒有任何標籤包含逗號、沒有重量超出容量、沒有重量為零或負數、沒有價值為非有限值；計算機會明確拒絕這些輸入。
- 執行求解器。結果面板會列出所有被選中的標籤、總價值、所用總重量，以及未使用的容量。
- 檢視選中的項目；若需要可將其複製為純文字，再貼到報告或試算表中。
面板背後的動態規劃會建立一張表，每個物品對應一列、每個容量單位對應一行（從 0 一直到你輸入的容量）。對每個 (物品，容量) 儲存格，它會比較「不納入當前物品時可達到的最佳價值」與「納入當前物品再加上相容的先前狀態之最佳價值」，並保留較大者。當兩個狀態的價值完全相同時，計算機會保留較早的決策而非任意切換，因此相同輸入必定產生相同的選擇。表格填滿後，求解器會回溯所有記錄下來的決策，找出實際入選的標籤。
若想更深入了解表格運作機制，如何逐步計算背包問題指南以小型數值範例展開說明了每一個動態規劃儲存格。
計算機回傳的內容與省略之處
輸出內容刻意設計為易於檢視：在一個區塊中顯示選中的標籤、一列包含價值與重量的總計，以及底部的未使用容量。沒有評分系統、沒有信賴區間、沒有啟發式建議——僅有你輸入的有界模型之可證明最佳解。選中的項目可複製為純文字，並放入任何文件中。
輸出中「不包含什麼」同樣重要。它不包含實體尺寸、平衡限制、易碎性、物品互動、強制群組、不相容配對、期限、風險或不確定性。計算機內建的經典 10 容量測試即體現了此原則：給定重量與價值為 4 與 40、3 與 50 的兩個物品，最佳解會兩個都選，價值合計 40 + 50 = 90，而不是依循簡化的輸入順序。
這正是這個模型能乾淨地適用於有界標量配置的原因——具明確投入預算的功能優先排序、小型投資組合範例、課堂習題、初步裁切清單——但只要約束條件變成非標量，就不再適用。
模型限制與適可而止的時機
0/1 計算機在三個方面有所限制，這對輸入設計十分重要。容量硬性上限為 10,000，清單上限為 100 個有標籤的不同物品，兩者都是為了避免表格超出瀏覽器記憶體。重量必須為整數，因為每個容量單位都對應一個動態規劃狀態；若你的測量單位帶有固定小數，請在輸入前一致地放大（例如將 2.5 公斤換算為 25 個十分位），並記得刻度越細，表格就越大。價值可以為零或正小數，且不必與重量共用單位，這讓你能在同一列上混用 effort points、美元或優先順序。
在課堂練習、有界功能優先排序、初期投資組合情境，以及權重確實為標量的小型配置問題等情況下，你應該在計算機的答案處畫下句點。但對於具有真實風險的財務投資組合、安全負載、醫療資源分配，或任何標量目標掩蓋了會改變正解之相依性的決策，則不應止步於此。在這些情況下，請先用領域專屬模型及可信賴的審查者驗證目標、限制與後果，再依所選子集合採取行動。
| 使用情境 | 符合計算機的 0/1 模型嗎？ |
|---|---|
| 固定 effort 預算下的功能優先排序 | 是 |
| 為配送卡車選取整箱貨物（標量重量） | 是 |
| 課堂用的 0/1 背包練習 | 是 |
| 具有風險相關性的投資組合最佳化 | 否 |
| 涉及尺寸、平衡或堆疊的箱體裝箱 | 否 |
| 含期限與衝突的排程 | 否 |
一旦確認問題確實是單一標量容量、不可分割物品的選擇，背包問題計算機便能一次給出可證明的最佳解；一旦不是，請將標量答案視為初步構想，並引進能涵蓋缺失維度的模型。
若想進一步了解，請參閱 直接在瀏覽器中求解最小生成樹。