装箱问题的近似解

装箱问题的近似解一、FFD(FirstFitStrategy)策略Firstfitstrategy:placesanobjectinthefirstbininwhichitfits.FFDstrategyisamodificationthatsortstheobjectsfirstsothattheyareconsideredinorderofnon-increasingsize.二、例P573三、算法13.1装箱问题-FFDbinpackFFD(S,n,bin)float[]used=newfloat[n+1];inti,j;SortSintodescendingorder;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(nlogn)+O(n(n-1)/2)O(n2)引理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,…,si1/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个箱子不含有objectk+1,…,i-1.则在最优解的情况下，objectk+1,…,i-1.将会被放在Bk+1,…,Bopt,并且它们中的每一个都被放入2个object。于是，第i个object被放置在前面的那个箱子呢？因为它的size1/3,所以放置在前面的那1箱子都不合适！利用“最优”情况导出矛盾引理13.10对任意输入S=(s1,s2,…,sn)，FFD放在附加箱子的object个数至多为opt(s)-1.证明因为，在最优情况下：•每个箱子的容量为1•箱子的个数为opt(s)反证：设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.11RFFD(m)4/3+1/(3m)无限的情况下：SFFD(m)3/2R和S的意义参见P572页证明设输入序列为(s1,s2,,sn)，opt(S)=m，则FFD放在附加箱子的object个数至多为opt(s)-1，它们至多占用（opt(s)-1）/3个箱子。则：RFFD(m)(m+(m-1)/3)/m1+(m+1)/3m4/3+(1/3m)