装箱问题的近似解.pptVIP

装箱问题的近似解 一、FFD(First Fit Strategy)策略 First fit strategy:places an object in the first bin in which it fits. FFD strategy is a modification that sorts the objects first so that they are considered in order of non-increasing size. 二、例 P573 三、算法13.1 装箱问题-FFD binpackFFD(S, n, bin) float[] used=new float[n+1]; int i,j; Sort S into descending order; for (i=1; i?n; i++) for(j=1; j?n; j++) if (used[j]+si ?1.0) bin[i]=j; used[j]+= si; break; 四、FFD算法的复杂性 O(n logn)+O(n(n-1)/2)? O(n 2) 引理13.9 设S=(s1, s2 , …, sn )为一个非递增序列，opt(S)是S所需要的最小箱包数，则所有被FFD放入附加箱(下标opt(S))的object的大小 至多为1/3。 证 明 证明： 设i为第一个被FFD放入opt(S)+1 的object的下标，要证明si?1/3。 反证： 设si1/3, 则s1, s2 , …, si 1/3，则箱子Bj ,0?j ? opt(s)至多包含2个object。 我们要证明存在k?0， k是第一个满足下列条件的箱子下标： 它只含有1个s1, s2 , …, si中的object，而余下的opt(s)-k个箱子中包含2个object。 反证： 设存在箱子Bp , Bq ，其中pq, Bp 中含有2个s1, s2 , …, si中的object, 分别为t和 u，其中 t ? u, 而Bq中仅有1个object ，为v 。 因为S是非递减序列，所以t ? v ， u ? si ，综合这2点，可以得出1 ?t+u ?v+ si ,则FFD就会把第i个object 放在箱子 Bq 中，与i= opt(s)矛盾。 所以存在k?0， k是第一个满足只含有1个object，而余下的opt(s)-k个箱子中包含2个object的箱子下标。 在最优解的情况下,所有object都会放置在opt(s) 个箱子中。 不失一般性，我们假定前k个箱子不含有object k+1 , …,i-1. 则在最优解的情况下， object k+1 , …,i-1.将会被放在Bk+1 , …, Bopt,并且它们中的每一个都被放入2个object。 于是，第i个object被放置在前面的那个箱子呢？因为它的size1/3,所以放置在前面的那1箱子都不合适！ 引理13.10 对任意输入S=(s1, s2 , …, sn )，FFD放在附加箱子的object个数至多为opt(s)-1. 证 明 因为， 在最优情况下： 反证：设FFD把opt(S)个objects放入附加箱，它们的大小分别为t1,t2, ?,topt(s) . 用bj表示箱子Bj的最后容量,1 ? j ? opt(s)。如果bj +ti ? 1，则FFD就可以把ti放入Bj中，但现在FFD把ti放入opt(s) 以后的桶中了，所以产生了下列矛盾的表达式： 定理13.11 RFFD(m)?4/3+1/ ( 3m) 无限的情况下： SFFD(m)?3/2 R和S的意义参见P572页 证 明 设输入序列为(s1,s2, ?,sn)，opt(S)=m，则FFD放在附加箱子的object个数至多为opt(s)-1，它们至多占用（opt(s)-1）/3个箱子。