Bin Packing Problem (Decision Version)
===
### 題目
### Lower Bound
所有 $m_i$ 加總後除以 M 即為最少需要的 Bin 數

例如 : 有 4 個容量為 7 的箱子，有 6 種物品，重量分別為 3, 1, 6, 4, 5, 2。
最少需要 (3 + 1 + 6 + 4 + 5 + 2) / 7 = 3 個 Bin
### First Fit Algorithm
每個物品從第 1 個箱子開始放，如果放不下就考慮第 2 個箱子，又放不下就考慮下一個箱子，依此類推，只要箱子有足夠空間放入物品就放進去。

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

優點 : 簡單
缺點 : 很難得到最佳解
### First Fit Decreasing Algorithm
先將物品容量由大到小排序，然後再執行 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
Full Bin Packing 的概念就是先找出能剛好塞滿箱子的物品再放入箱子，這樣就可以使空間浪費最少。

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

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

### 證明 Bin Packing Problem (Decision Version) 屬於 NPC
(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{2c_i}{\sum_{j=1}^{n}{c_j}} \in (0,1] \ for\ 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**。
### 參考
* [台大哥](https://sunprinces.github.io/learning/2017/08/advanced-algorithm---bin-packing-problem/)