如何使用Visual C++實(shí)現(xiàn)裝箱問題的BF算法

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

　　NP問題有好多個(gè)，裝箱問題是其中一個(gè)。設(shè)有體積分別為T1 ，T2 ， T3 ，…… Tn的m種貨品要裝容量為c 的箱子里。采用不同裝箱方法所需的箱子數(shù)可能不同［1］ 。要解決的問題是如何使用最少的箱子數(shù)將這 m 種貨品裝進(jìn)去。裝箱問題是 NP 問題，這是不容易得到一個(gè)最佳的解決方案，為了比較快速得到滿意解，近似算法經(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）近似算法等。

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

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