打包

建立「封裝」packing問題的目標，是找出將指定大小項目組合封裝到具有固定packing的容器中的最佳做法。一般的應用程式是有效率地將箱子載入運送貨車。通常因為容量限制，您無法封裝所有項目。在這種情況下，問題是找出總大小足以容納容器的項目子集。

封裝問題有很多種，其中兩個最重要的是「刀具問題」和「分裝」。

Knapsack 問題

這個簡單的刀械攻擊問題有一個容器 (指刀)。這些項目都有值和尺寸，而目標是封裝具有最高總值的項目子集。

針對值等於大小的特殊情況，目標是最大化包裝項目的總大小。

OR-Tools 在其演算法程式庫中提供了多個 Knaps 問題的解題工具。

還有較籠統的刀具問題。以下是一些範例：

• 多維度旋鈕問題：該項目具有多個實體數量 (例如重量和體積)，且指針在每種數量都有其容量。此處的「維度」一詞不一定是指高度、長度和寬度的一般空間維度。不過，有些問題可能會涉及空間維度，例如找出將矩形封裝至矩形儲存空間特徵分塊的最佳方式。

• 多個刀類問題：這類問題有多個刀械，目標是要讓所有刀類中的包裝項目總價值最大化。

請注意，有可能是單一刀環所構成的多維問題，或只有一個維度的多個針狀問題。

分裝箱問題

「分裝」bin-packing是最常見的封裝問題之一，其中有多個容器 (稱為「bins」bin-packing) 具有相同的容量。與多個刀環問題不同，繫結數量並未修正。相反地，目標是找出用來存放所有項目的最小特徵分塊。

以下的簡單範例說明多個刀口問題與分裝包裝問題之間的差異。假設某間公司有送貨車，每輛車的重量分別是 18,000 磅，以及 13 萬 13 萬磅要交付的商品。

• 多個刀環：你有 5 輛卡車，想要載入最大重量項目的部分。

• 特徵分塊：您擁有 20 輛卡車 (超過所有物品的數量都足以存放所有物品)，而您想要使用的卡車數量最少。

下列各節將說明如何使用 OR-Tools 解決各種封裝問題，從「Kenapsack 問題」開始。