装箱问题与背包问题ppt课件.ppt

一、装箱问题（bin packing problem）当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合优化问题，即使用计算机也是不容易解决的。,装箱问题是一个经典的NP难解问题，这意味着该问题不存在在多项式时间内求得精确解的算法（如果PNP）,因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果,但不一定得到精确解。,其在工业生产及日常生活中有广泛的用途，其应用在实际生活中无处不在，货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以具有重要的研究价值。,【问题】 装箱问题问题描述：装箱问题可简述如下：设有编号为1、n的n种物品，体积分别为v1、v2、vn。将这n种物品装到容量都为V的若干箱子里(更一般的装箱问题还可以要求容量不是相同的)。约定这n种物品的体积均不超过V，即对于1i n，有0viV。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。,装箱问题的数学表示如下（ 0-1规划模型）：,s.t.,yi =1表示箱子i装入物品，反之表示箱子i空着,xij =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软件求解,装箱问题的近似求解算法,NF（Next Fit下次适应）算法：按照物体给定的顺序装箱：把物品wi放到它第一个能放进去的箱子中。Bj是具有最大下标的使用过的箱子，若wi的长度不大于Bj的剩余长度，则把wi放入Bj，否则把wi放入一个新的箱子Bj+1，且Bj在以后的装箱中不再使用。最后循环,FF（First Fit首次适应 ）算法：按照物体给定的顺序装箱：把物品wi放到第一个箱子中。 B1 B2 Bj是当前已经使用过的箱子，在这些箱子中找一个长度不小于wi且下标最小的箱子,将放入wi，如果不存在这样的箱子,则另开一个新箱子Bj+1 , 将wi放入Bj+1中 。,在线算法：如果一个近似装箱算法在执行过程中，每当一个物品到达时，就立刻决定把该物品放入哪个箱子中，而不管后序物品如何，这种算法就被称为在线算法。下次适应算法、首次适应算法等都是在线算法，其时间复杂度都为O(n) 。,以上算法都称为在线适应算法，适应算法的特点是当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子。,不失一般性，对n件物品的体积按从大到小排好序，即有v1v2vn，然后按排序结果对物品重新编号即可。,降序首次适应算法 （FFD）:先将物体按长度从大到小排序,然后按FF算法对物体装箱.,离线算法：如果算法在开始装箱之前，已经预先得到了所有物品的信息而一次性的确定装箱策略，这种算法就被称为离线算法。降序首次适应算法和降序最佳适应算法是两个重要的离线算法。这里的降序首次适应算法就是一种贪婪算法。,FFD算法： 输入箱子的容积； 输入物品种数n； 按体积从大到小顺序，输入各物品的体积； 预置已用箱子链为空； 预置已用箱子计数器box_count为0； for (i=0;in;i + ) 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j； if （已用箱子都不能再放物品i） 另用一个箱子，并将物品i放入该箱子； box_count+； else 将物品i放入箱子j； ,装箱问题中最早被研究的是一维装箱问题。随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。但是由于这些问题所与生俱来的复杂性，虽然已经有一些研究成果发表了，但是其研究还是相当的困难。本文所讨论的还是一维装箱问题。,装箱问题在工业生产及日常生活中有广泛的用途，其应用在实际生活中无处不在，如货物装运，服装裁剪，以及我们计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。所以具有重要的研究价值。,例2: 多处理器调度问题 设有n个独立的作业1,2,n，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。 多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 分析这个问题可以看成装箱问题，也是NP完全问题。对于这一类问题，用贪婪选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪婪选择策略可以设计出解多处理器调度问题的较好的近似算法。按此策略，当nm时，我们只要将机器i的0,ti时间区间分配给作业i即可。 当nm时，我们首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理器。,例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1,M2,和M3来加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按贪婪算法产生的作业调度如图所示，所需的加工时间为17。,当nm时，因此算法所需的计算时间复杂度为O(nlogn)。,例如,一个软件开发小组要在规定时间内完成一项任务,系统分析员把任务划分成各个子任务.由于每个子任务要求的花费程序员的时间不同,不合理的分派将导致各程序员贻误工期. 这就是一个多处理器调度问题的应用。,二、一维0/1背包问题设有n=8个体积分别为54，45，43，29，23，21，14，1的物体和一个容积为C=110的背包，问选择哪几个物体装入背包可以使其装的最满。 如直接用贪婪算法，将物体由大到小顺次装入背包，到装不下时再逐个试装更小的一些，直至试到最小的一个或装满为止。按此处所给数据，先装入54和45两个，容积尚余11，最后只能再装入体积为1的一个，总体积达到100，并不算太满。此方法的好处是节省时间，主要的运算时间是用来对n个元素进行排序，故其复杂性是O（nlogn）。,如果对上述算法作一些改进，可得到更好的结果。先从n个物体中试着取j个总体积不超过C的装入背包，剩下的(n-j)个物体则利用贪婪算法尽量往里装。此j值从零开始逐渐增加，反复进行试探，直至j达到某预先给定的常数k(0kn)，最后从这些结果中取其最好的一个。如果在试探中能得到一个完全装满的方案，则此过程就可提前结束。因为从n个物体中取出j个共有 种方案，此值随着j的增加而增加较快，但可以证明此改进算法的复杂性为O（knk+1）,因k是常数，故仍为多项式界的算法。,按本例所给数值，取j=0时，因就是前述普通贪婪算法，已经得到100的结果；取j=1时，共有8种方案，当用29或23先装入时，可得到54+29+23+1=107的更好结果；取j=2时，共有28种方案，其中有能将背包完全装满的结果（43+23+29+14+1=110）。故知此问题当取k2时就可得到最优解。,当n不太大时，适当的取k值，此改进方法常常可以得到最优解，但不能因此就说一般背包问题有多项式算法。当n增大时，k不能随着n不断的加大，如k随n增大而同时加大，其复杂性就是指数型而不是多项式型的了，而如k取值较小，又不能保证得出最优解。,求将哪些物品装入背包可在满足背包容量允许的前提下使价值总和最大。,背包问题也是经典的NP-hard组合优化问题之一,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。,一维0/1背包问题的数学提法：,背包问题的数学模型描述如下：,问题自身的特性决定了该问题运用贪婪算法可以得到最优解或较优解。通常这里有三种贪婪准则:,1、价值贪婪准则：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去，这种策略不能保证得到最优解。2、质量贪婪准则：从剩下的物品中选择可装入背包的重量最小的物品，在一般情况下也不一定能得到最优解。3、价值密度贪婪准则：从剩余物品中选择可装入包的cj /wj 值最大的物品，即按cj/wj 非递增的次序装入物品，只要正被考虑的物品装得进就装入背包，这种策略可能会得到最优解。,例：“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3 , 奖品i占用的空间为widm3 ,价值为vi 元, 具体的数据如下:vi = 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1wi = 80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1。,(1)输入物品个数n, 背包的容量limitW, 每个物品的重量wj 和价值cj。(2)对物品按单位价值从大到小排序。,(3)将排序后的物品依次装入背包。对于当前物品j,若背包剩余可装重量大于或等于wj , 则将物品j装入背包, 继续考虑下一个物品j+1, 重复步骤3,否则得到问题的解,输出。,算法流程,注：1、算法主要的运算时间是用来对n个元素进行排序，故其复杂性是O（nlogn）。2、对于解决0/1背包问题，总得来讲，动态规划比贪婪算法要好些，可以得到最优解。,