基于Visual C++的装箱问题的BF算法

黄鸿华

摘要：装箱问题是NP问题。该文对装箱问题的BF算法进行了分析，用Visual C++实现该算法。

关键词：装箱问题;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问题有好多个，装箱问题是其中一个。设有体积分别为T1 ，T2 ， T3 ，…… Tn的m种货品要装容量为c 的箱子里。采用不同装箱方法所需的箱子数可能不同[1]。要解决的问题是如何使用最少的箱子数将这m种货品装进去。装箱问题是NP问题，这是不容易得到一个最佳的解决方案，为了比较快速得到满意解，近似算法经常被使用。常见的算法[2]：NF（Next Fit）近似算法，BF（Best Fit）算法，BFD（Best Fit Deceasing）算法，FF（First Fit）近似算法，FFD（First Fit Decreasing）近似算法等。

2 装箱问题的集中常见算法[3]

下次适应算法NF（Next Fit）：最简单也是最早研究的算法是NF算法。它的特点是至始至终保持一个当前打开的箱子，在要将货品装入到箱子时，查看这个货品能不能装入到当前打开的箱子，如果可以则装入。如果没有办法装进去，就新打开一个空的箱子作为当前的箱子，将货品装入。这个算法装箱的效率不高，原因是只有现在打开的箱子和空的箱可以作为选择装入货品。

最佳适应算法BF（Best Fit）：在装入货品时装入到最合适这个货品的箱子里，这个箱子不是第一个可装的箱子，而是最合适的。当没有适合该物体的箱子时，打开一个空箱子。

降序最佳适应算法BFD（Best Fit Deceasing）：是按照BF（Best Fit）算法进行装箱，不过该算法会先对货品按容量从大到小进行排序。

首次适应算法FF（First Fit）：和下次适应算法的不同，FF算法要先检查所有非空的箱子，如果第一个非空箱子能放进去该货品则放入，没办法放入的话再检查第二个非空箱子，以此类推;如果没有合适的箱子，就打开一个空的箱子。

降序首次适应算法FFD（First Fit Decreasing）：是按照FF（First Fit）算法进行装入箱子，不同之处会对先对货品按容量从大到小进行排序。

一些学者提出了最佳适应算法和首次适应算法的改进算法。我们观察首次适应算法和最佳适应算法，货品是随机的没有降序排列，会发生容量大的排列，装不进去，原因是可能先装了小的货品，只能再开启新的箱子，使空间的没有充分利用。

3 Best Fit算法

Best Fit 的基本思想[1]是： n 种货品依次放入箱子，将货品i 装入箱子j应满足 c - cj- vi= min {c- ck- vi} c- ck-vi>=0，即选取第j号箱子，使得装入货品i后所留空隙最小，其中ck表示已装入第k号箱子的货品的体积[1]。把每个货品的与箱子的容量的差值存在链表数组里，（链表的结点存放货品的号码）插入每一个货品时就可以直接先找到与之容量相同的箱子和可以与之同放一个箱子的货品号码，并把那箱子删掉;若容量相同的箱子没有剩，就找比它大的箱子，把原结点删掉，并把还有空间剩下的箱子插入的相应的链表里;若已经没有比它大的箱子，就开辟新的箱子。

4 C++实现算法

#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 算法分析

该算法的思路是从第一个数据开始进容器，然后每个数据都把所有容器里面的数遍历一遍，把数据加到满足题目这个公式的加到容器的那个数据里面，如果容器中有装满的，就把它弹出容器，以免浪费空间。BF算法的时间复杂度为O（n2），空间复杂度为O（n）。

参考文献：

[1] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2004.

[2] 孙春玲，陈智斌，李建平.装箱问题的一种新的近似算法[J].云南大学学报： 自然科学版，2004，26（5）：392-396.

[3] 刘辉.装箱问题的概率近似算法[J].科学技术与工程，2007（13）.

[通联编辑：谢媛媛]