1.3装箱问题与背包问题PPT参考课件.ppt

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