裝箱演算法是一種決策規則,將不可分割的項目指派給固定容量的箱子,同時盡量減少使用的箱子數量並避免超出容量限制。
在標準的一維模型中,每個項目都有單一的正純量大小,每個箱子都有相同的容量,且項目不可分割。目標是將每個項目恰好指派一次,使每個箱子都不超過容量,並使用盡可能少的箱子。裝箱演算法可以是精確最佳化方法,也可以是速度較快的啟發式方法。首次配合遞減法(First Fit Decreasing,FFD)是 Bin Packing Calculator 所採用的確定性啟發式方法。

演算法背後的目標
核心裝箱問題包含四項要求:
- 所有箱子都有相同的容量。
- 每個項目都完整地指派給恰好一個箱子。
- 任何箱子內的項目大小總和都不超過其容量。
- 開啟的箱子數量盡可能少。
此目標可表述為:在維持這些限制條件的同時,盡量減少箱子數量。簡單的大小下界為 ceil(項目總大小 ÷ 容量)。它只依據總需求估算無可避免的箱子數量,但未考慮特定項目大小可能無法恰好組合至可用空間中的情況。
| 方法 | 決策方式 | 結果所建立的內容 |
|---|---|---|
| 首次配合遞減法 | 依大小遞減排序項目,並使用第一個有足夠空間的已開啟箱子。 | 一種確定性且可行的指派,但不保證使用最少數量的箱子。 |
| 精確最佳化模型 | 在強制套用容量與指派限制的同時,搜尋項目至箱子的指派方式。 | 當求解器能夠完成最佳化證明時,取得最少箱子數量。 |
首次配合遞減法如何做出決策
FFD 會套用一連串簡短規則,而非測試所有可能的配置:
- 以穩定方式將項目由大到小排序。大小相同的項目會保留原始輸入順序。
- 依箱子開啟的順序進行檢查。
- 將目前項目放入第一個有足夠剩餘容量的已開啟箱子。
- 如果沒有任何已開啟的箱子能容納該項目,就開啟一個新箱子。
此處的 首次是指最早開啟的箱子,而不是剩餘空間最小或使用率最高的箱子。此區別可讓結果具備可重現性,也能讓您追蹤某個項目為何被放入特定箱子。每次使用相同容量與項目清單,都會產生相同的 FFD 指派結果。
當快速且一致的分組比全域最佳化證明更重要時,FFD 相當實用。它的弱點在於,早期的配置可能留下某種組合,而該組合原本能支援更整體的更佳配置。
在計算工具中建立 FFD 方案
- 開啟 Bin Packing Calculator,並輸入每個箱子可用的共同容量。介面本身會強制套用容量上限。
- 在每一行輸入一個項目。每一列只能包含大小,例如 12;或是一個標籤加上一個逗號與大小,例如 Memory block A, 12。容量與每個項目都必須使用相同單位。清單最多可接受 1,000 個項目,而標籤長度有限。僅含數字的列會自動取得標籤;自訂標籤內的逗號不符合這個簡易匯入格式。
- 執行 FFD 並檢查每個箱子。確認每個項目都只出現一次,比較已使用與剩餘容量,並在接受分組前檢視整體使用率與簡易大小下界。
- 如果方案適合工作表、載入草稿、記憶體配置範例或作業研究練習,就複製該方案。計算工具會指派不超過容量且大小為正的項目,並對無效或過大的輸入項目回報清楚的錯誤訊息。
所有處理都在瀏覽器中完成,因此不需要上傳容量與項目清單。FFD 程序及其產生的指派結果都是確定性的。
解讀箱子數量、使用率與下界
輸出包含數個彼此相關的數值。每個數值衡量的內容不同,因此不應將它們視為可以互換。
| 輸出 | 解讀方式 | 重要限定條件 |
|---|---|---|
| 開啟的箱子 | FFD 方案所使用的箱子數量。 | FFD 使用的箱子可能比全域最佳配置更多。 |
| 項目指派 | 每個項目所收到的箱子。 | 每個項目都完整地指派給恰好一個箱子。 |
| 已使用與剩餘容量 | 每個箱子已消耗與仍可使用的純量容量。 | 剩餘容量是模型中的未使用空間,不一定是能回收的實體體積。 |
| 整體使用率 | 項目總大小除以所有已開啟箱子的總容量。 | 這是一項彙總指標,不能證明該指派在全域方面是最佳的。 |
| 大小下界 | ceil(項目總大小 ÷ 容量)。 | 沒有任何解決方案能使用更少的箱子,但僅憑此下界無法證明顯示的方案是最佳方案。 |
以單一下界計算為例,假設項目總大小為 17,容量為 10,結果為 ceil(17 ÷ 10) = ceil(1.7) = 2 個箱子。這排除了使用單一箱子的解決方案,但無法識別每個項目的所有可行組合,因此計算工具會將此數值呈現為下界,而不是最佳化證明。
當 FFD 開啟的箱子多於下界時,差異可能反映不可分割的項目組合、可避免的局部配置,或兩者皆有。這表示僅靠總大小無法解釋結果,但也無法透露窮舉搜尋需要多少個箱子。
模型能與不能表示的內容
此演算法使用抽象的純量數值。只要容量與所有項目大小都使用相同單位,這些數值便可表示重量、記憶體、工作負載、長度或其他一維資源。這讓模型有助於在套用領域特定規則前,探索批次分組、資源指派與排序效應。
計算工具不會模擬數項重要的現實限制:
- 它不具備三維尺寸、方向、平衡、易碎性、堆疊強度、重心、危險品隔離或車輛軸重限制。
- 它無法分割項目、合併容量、預留空間,或套用項目價值與優先順序。
- 它無法產生最低成本或安全的實體裝載方案證明。
例如,項目大小為 10 並未描述一個具有長度、寬度與高度的箱子。廣泛的容器裝載決策需要專業軟體、有紀錄的安全規則,以及對最終指派的驗證。物流、雲端容量、製造與安全關鍵應用,也應使用適當且經過驗證的求解器進行檢查,而不是僅依賴這個一維啟發式方法。
選擇 FFD 或精確最佳化
當可行方案與透明的稽核軌跡就已足夠時,FFD 適合用於快速且可重現的分組。如果必須確定最少箱子數量本身,請使用會搜尋替代指派方式的最佳化求解器。Google OR-Tools 的裝箱文件說明了項目至箱子的限制與最少箱子目標。
其他目標需要不同的模型。如果庫存可以切割成不同的所需 piece,該任務就是裁料問題,而非不可分割項目的裝箱問題;Lehigh University 對裁料問題的分析說明了該問題的表述方式。同樣地,價值、預留容量、多個資源維度與排程優先順序,會衍生背包、多重背包或排程變體,而這些都不是此計算工具能解決的問題。