裝箱問題是NP問題。該文對裝箱問題的BF算法進行了分析，用Visual C++實現(xiàn)該算法。

　　NP問題有好多個，裝箱問題是其中一個。設(shè)有體積分別為T1 ，T2 ， T3 ，…… Tn的m種貨品要裝容量為c 的箱子里。采用不同裝箱方法所需的箱子數(shù)可能不同［1］ 。要解決的問題是如何使用最少的箱子數(shù)將這 m 種貨品裝進去。裝箱問題是 NP 問題，這是不容易得到一個最佳的解決方案，為了比較快速得到滿意解，近似算法經(jīng)常被使用。常見的算法［2］ ：NF（Next Fit）近似算法，BF（Best Fit）算法，BFD（Best Fit Deceasing）算法，F(xiàn)F（First Fit）近似算法，F(xiàn)FD（First Fit Decreasing）近似算法等。

　　下次適應算法NF（Next Fit）：最簡單也是最早研究的算法是 NF算法。它的特點是至始至終保持一個當前打開的箱子，在要將貨品裝入到箱子時，查看這個貨品能不能裝入到當前打開的箱子，如果可以則裝入。如果沒有辦法裝進去，就新打開一個空的箱子作為當前的箱子，將貨品裝入。這個算法裝箱的效率不高，原因是只有現(xiàn)在打開的箱子和空的箱可以作為選擇裝入貨品。最佳適應算法BF（Best Fit）：在裝入貨品時裝入到最合適這個貨品的箱子里，這個箱子不是第一個可裝的箱子，而是最合適的。當沒有適合該物體的箱子時，打開一個空箱子。降序最佳適應算法BFD（Best Fit Deceasing）：是按照BF（Best Fit）算法進行裝箱，不過該算法會先對貨品按容量從大到小進行排序。首次適應算法FF（First Fit）：和下次適應算法的不同，F(xiàn)F算法要先檢查所有非空的箱子，如果第一個非空箱子能放進去該貨品則放入，沒辦法放入的話再檢查第二個非空箱子，以此類推；如果沒有合適的箱子，就打開一個空的箱子。降序首次適應算法 FFD（First Fit Decreasing）：是按照 FF （First Fit）算法進行裝入箱子，不同之處會對先對貨品按容量從大到小進行排序。一些學者提出了最佳適應算法和首次適應算法的改進算法。我們觀察首次適應算法和最佳適應算法，貨品是隨機的沒有降序排列，會發(fā)生容量大的排列，裝不進去，原因是可能先裝了小的貨品，只能再開啟新的箱子，使空間的沒有充分利用。

　　Best Fit 的基本思想是：n 種貨品依次放入箱子，將貨品i 裝入箱子j應滿足 c - cj- vi= min {c- ck- vi} c- ck-vi》=0，即選取第j號箱子，使得裝入貨品i后所留空隙最小，其中ck表示已裝入第k號箱子的貨品的體積 。把每個貨品的與箱子的容量的差值存在鏈表數(shù)組里，（鏈表的結(jié)點存放貨品的號碼）插入每一個貨品時就可以直接先找到與之容量相同的箱子和可以與之同放一個箱子的貨品號碼，并把那箱子刪掉；若容量相同的箱子沒有剩，就找比它大的箱子，把原結(jié)點刪掉，并把還有空間剩下的箱子插入的相應的鏈表里；若已經(jīng)沒有比它大的箱子，就開辟新的箱子。