Bin Packing Problem (Decision Version)

Image Not Showing Possible Reasons

所有

m_{i}

加總後除以 M 即為最少需要的 Bin 數

例如 : 有 4 個容量為 7 的箱子，有 6 種物品，重量分別為 3, 1, 6, 4, 5, 2。
最少需要 (3 + 1 + 6 + 4 + 5 + 2) / 7 = 3 個 Bin

每個物品從第 1 個箱子開始放，如果放不下就考慮第 2 個箱子，又放不下就考慮下一個箱子，依此類推，只要箱子有足夠空間放入物品就放進去。

同上例，執行結果如下，總共需要 4 個箱子，但還不到最佳解。
B1: 3, 1, 2
B2: 6
B3: 4
B4: 5

優點 : 簡單
缺點 : 很難得到最佳解

先將物品容量由大到小排序，然後再執行 First-fit Algorithm。

同上例，執行結果如下，總共需要 3 個箱子，剛好得最佳解。
物品放入順序為 : 6, 5, 4, 3, 2, 1
B1: 6, 1
B2: 5, 2
B3: 4, 3
B4:

優點 : 簡單且比 First Fit 更好
缺點 : 不一定會得到最佳解

Full Bin Packing 的概念就是先找出能剛好塞滿箱子的物品再放入箱子，這樣就可以使空間浪費最少。

同上例 : 總共需要 3 個箱子，剛好得到最佳解。
3 + 4 = 7 => 放入 B1
1 + 6 = 7 => 放入 B2
2 + 5 = 7 => 放入 B3

優點 : 離最佳解最近
缺點 : 如果數字很醜的話，要做到 Full Bin 有點難

(1)
給定一組 instance 很容易在多項式時間內驗證此 n 個物品能用 k 個箱子裝完，故屬於 NP

(2)
已知 2-PARTITION 屬於 NPC
可以從 2-PARTITION 問題轉換成 Bin Packing (Decision Version)

給定一組 2-PARTION 的 instance : 存在一組集合

S \subseteq {1, . . ., n}

使得

\sum_{i \in S} c_{i} = \sum_{i \notin S} c_{i}

我們可以將此 instance 轉成 Bin Packing 的 instance。
建構方式 :

給定 k = 2，箱子容量 M = 1
設定每種物品容量
$m_{i} = \frac{2 c_{i}}{\sum_{j = 1}^{n} c_{j}} \in (0, 1] f o r i = 1, . . ., n$ ，

很明顯地我們可以利用 2 個容量為 1 的箱子裝完這 n 個物品，故可推得以下定理 :

Theorem : It is NP-complete to decide if an instance of Bin Packing admits a solution with two bins.

如果 Bin Packing (Decision Version) 的 instance 可以利用 2 個箱子就裝滿所有物品，則此問題屬於 NPC。

註 : Bin Packing 屬於 NP-hard，但 Decision Version 為 NPC。