基于Visual C++的裝箱問題的BF算法

黃鴻華

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

關(guān)鍵詞：裝箱問題;BF算法

中圖分類號：TP311? ? ? 文獻標識碼：A? ? ? 文章編號：1009-3044（2018）36-0258-02

Abstract：The packing problem is a classic NP problem.In this paper，the packing problem and its algorithm is analyzd，the algorithms is Based on BF algorithm.? And carry out that algorithms in the Visual C++.

Key words：packing problem; BF algorithm

1 裝箱問題

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）近似算法等。

2 裝箱問題的集中常見算法[3]

下次適應(yīng)算法NF（Next Fit）：最簡單也是最早研究的算法是NF算法。它的特點是至始至終保持一個當前打開的箱子，在要將貨品裝入到箱子時，查看這個貨品能不能裝入到當前打開的箱子，如果可以則裝入。如果沒有辦法裝進去，就新打開一個空的箱子作為當前的箱子，將貨品裝入。這個算法裝箱的效率不高，原因是只有現(xiàn)在打開的箱子和空的箱可以作為選擇裝入貨品。

最佳適應(yīng)算法BF（Best Fit）：在裝入貨品時裝入到最合適這個貨品的箱子里，這個箱子不是第一個可裝的箱子，而是最合適的。當沒有適合該物體的箱子時，打開一個空箱子。

降序最佳適應(yīng)算法BFD（Best Fit Deceasing）：是按照BF（Best Fit）算法進行裝箱，不過該算法會先對貨品按容量從大到小進行排序。

首次適應(yīng)算法FF（First Fit）：和下次適應(yīng)算法的不同，F(xiàn)F算法要先檢查所有非空的箱子，如果第一個非空箱子能放進去該貨品則放入，沒辦法放入的話再檢查第二個非空箱子，以此類推;如果沒有合適的箱子，就打開一個空的箱子。

降序首次適應(yīng)算法FFD（First Fit Decreasing）：是按照FF（First Fit）算法進行裝入箱子，不同之處會對先對貨品按容量從大到小進行排序。

一些學者提出了最佳適應(yīng)算法和首次適應(yīng)算法的改進算法。我們觀察首次適應(yīng)算法和最佳適應(yīng)算法，貨品是隨機的沒有降序排列，會發(fā)生容量大的排列，裝不進去，原因是可能先裝了小的貨品，只能再開啟新的箱子，使空間的沒有充分利用。

3 Best Fit算法

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

4 C++實現(xiàn)算法

#include<iostream.h>

class node

{friend class list;

public：

int data;

node *next;

};

class list{

public：

node *first;

list（）

{first=0;

}list&insert（int k，int x）;

list&Delete（int &x）;

};

list&list：：insert（int k，const int x）

{? node *p=first;

for（int index=1;index<k&&p;index++）

p=p→next;

node *y=new node;

y→data=x;

if（k）

{y→next=p→next;

p→next=y;

}else

{y→next=first;

first=y;

}return *this;

}

list&list：：Delete（int&x）

{? ?node *p=first，*trail=0;

while（p&&p→data！=x）

{ trail=p;

p=p→next;

}x=p→data;

if（trail）

trail→next=p→next;

else

first=p→next;

delete p;

return *this;

}int main（）

{? int i，j，n，c，count=1，t，v;

ifstream fin（"input.txt"）;

ofstreamfout（"output.txt"）;

fin>>n>>c;

list *list_bx=new list[c+1];

fin>>v;

if（v>c）

{fout<<"No Solution！"<<endl;

return 0;

}if（n>0）

list_bx[c-v].insert（0，1）;

if（n>1）

{for（i=2;i<n+1;i++）

{? ?fin>>v;

if（v>c）

{fout<<"No Solution！"<<endl;

return 0;

}for（j=v;j<c+1;j++）

{ if（list_bx[j].first）

{ t=list_bx[j].first→data;

list_bx[j].Delete（t）;

if（j-v）

list_bx[j-v].insert（0，t）;

break;

} if（j==c）

{ ++count;

list_bx[c-v].insert（0，i）;

} } }}

fout<<count<<endl;

fin.close（）;

fout.close（）;

return 0;

}

5 測試

在Visual C++ 下對該算法進行測試。輸入文件input.txt，輸出文件output.txt。

input.txt：

10 6

3 4 4 3 5 1 2 5 3 1

output.txt：

6

箱子1 ：? 1? ? ? ? ? ? ? ? ? 空間剩3

箱子2 ：? 2? ? ? ? ? ? ? ? ? 空間剩2

箱子3 ： 3? ? ? ? ? ? ? ? ? 空間剩2

箱子1 ： 1? ? ? ?4? ? ? ? ? 空間剩0

箱子4 ： 5? ? ? ? ? ? ? ? ? 空間剩1

箱子4 ：5? ? ? ? ? ? ? ? ? 空間剩1

箱子3 ： 3? ? ? ?7? ? ? ? ? 空間剩0

箱子5 ： 8? ? ? ? ? ? ? ? ? 空間剩1

箱子6 ： 9? ? ? ? ? ? ? ? ? 空間剩3

箱子5 ： 8? ? ?10? ? ? ? ? ?空間剩0

6 算法分析

該算法的思路是從第一個數(shù)據(jù)開始進容器，然后每個數(shù)據(jù)都把所有容器里面的數(shù)遍歷一遍，把數(shù)據(jù)加到滿足題目這個公式的加到容器的那個數(shù)據(jù)里面，如果容器中有裝滿的，就把它彈出容器，以免浪費空間。BF算法的時間復(fù)雜度為O（n2），空間復(fù)雜度為O（n）。

參考文獻：

[1] 王曉東.計算機算法設(shè)計與分析[M].北京：電子工業(yè)出版社，2004.

[2] 孫春玲，陳智斌，李建平.裝箱問題的一種新的近似算法[J].云南大學學報： 自然科學版，2004，26（5）：392-396.

[3] 劉輝.裝箱問題的概率近似算法[J].科學技術(shù)與工程，2007（13）.

[通聯(lián)編輯：謝媛媛]