装箱问题与背包问题.pptVIP

装箱问题（bin?packing?problem）当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合优化问题，即使用计算机也是不容易解决的。装箱问题是一个经典的NP难解问题，这意味着该问题不存在在多项式时间内求得精确解的算法（如果P≠NP）,因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果,但不一定得到精确解。其在工业生产及日常生活中有广泛的用途，其应用在实际生活中无处不在，货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以具有重要的研究价值。【问题】装箱问题问题描述：装箱问题可简述如下：设有编号为1、…、n的n种物品，体积分别为v1、v2、…、vn。将这n种物品装到容量都为V的若干箱子里(更一般的装箱问题还可以要求容量不是相同的)。约定这n种物品的体积均不超过V，即对于1≤i≤n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。1201装箱问题的数学表示如下（0-1规划模型）：02t.03yi=1表示箱子i装入物品，反之表示箱子i空着04xij=1表示物品j装入箱子i，反之表示物品j未放入箱子i若考察将n种物品的集合分划成n个或小于n个物品的所有子集，最优解就可以找到。但所有可能划分的总数太大。对适当大的n，找出所有可能的划分要花费的时间是无法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。见lingo程序例1已知30个物品,其中6个长0.51m，6个长0.27m，6个长0.26m，余下12个长0.23m，箱子长为1m，问最少需多少个箱子才能把30个物品全部装进箱子。装箱问题的LINGO软件求解010203NF（Next?Fit－下次适应）算法：按照物体给定的顺序装箱：把物品wi放到它第一个能放进去的箱子中。Bj是具有最大下标的使用过的箱子，若wi的长度不大于Bj的剩余长度，则把wi放入Bj，否则把wi放入一个新的箱子Bj+1，且Bj在以后的装箱中不再使用。1最后循环2装箱问题的近似求解算法FF（First?Fit－首次适应）算法：按照物体给定的顺序装箱：把物品wi放到第一个箱子中。B1B2…Bj是当前已经使用过的箱子，在这些箱子中找一个长度不小于wi且下标最小的箱子,将放入wi，如果不存在这样的箱子,则另开一个新箱子Bj+1,将wi放入Bj+1中。以上算法都称为在线适应算法，适应算法的特点是当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子。在线算法：如果一个近似装箱算法在执行过程中，每当一个物品到达时，就立刻决定把该物品放入哪个箱子中，而不管后序物品如何，这种算法就被称为在线算法。下次适应算法、首次适应算法等都是在线算法，其时间复杂度都为O(n)。01020101020304不失一般性，对n件物品的体积按从大到小排好序，即有v1≥v2≥…≥vn，然后按排序结果对物品重新编号即可。先将物体按长度从大到小排序,然后按FF算法对物体装箱.降序首次适应算法（FFD）:离线算法：如果算法在开始装箱之前，已经预先得到了所有物品的信息而一次性的确定装箱策略，这种算法就被称为离线算法。降序首次适应算法和降序最佳适应算法是两个重要的离线算法。05这里的降序首次适应算法就是一种贪婪算法。FFD算法：{输入箱子的容积；

输入物品种数n；

按体积从大到小顺序，输入各物品的体积；

预置已用箱子链为空；

预置已用箱子计数器box_count为0；

for(i=0;in;i++){从已用的第一只箱子开始顺序寻找能放入物品i的箱子j；

if（已用箱子都不能再放物品i）

{另用一个箱子，并将物品i放入该箱子；

box_count++；}

else

将物品i放入箱子j；

}}装箱问题中最早被研究的是一维装箱问题。随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。但是由于这些问题所与生俱来的复杂性，虽然已经有一些研究成果发表了，但是其研究还是相当的困难。本文所讨论的还是一维装箱问题。装箱问题在工业生产及日常生活