论文导读：装箱问题要求把一个给定了大小的物件序列装入一些容量为1的箱子，使得所用箱子数目尽可能少。本文主要研究的是装箱问题的一类衍生问题——染色装箱问题。
关键词：装箱问题，染色装箱，近似算法
一、引言
装箱问题要求把一个给定了大小的物件序列装入一些容量为1的箱子，使得所用箱子数目尽可能少。近一个多世纪以来，装箱问题已经在实际生产、生活中显示出重要的应用价值，故装箱问题已经广泛的为人们所研究，随着对装箱问题的更深的研究，其一系列衍生问题也逐步出现并被关注和加以探究。免费论文。本文主要研究的是装箱问题的一类衍生问题——染色装箱问题。
染色装箱问题是指：任意给定一个物件序列L = ( ， ，…， )。每个物件的大小 ∈(0，1]，其中 =1，2，…，n，每个物件有一个颜色 ∈N，此处有一些容量为1的箱子。染色装箱问题要求给出一种方案，把物件，，…，全部放入上述容量为1的某些箱子中，且每个箱子中所装物件颜色必须相同，使得所用箱子数目最少。免费论文。
二、染色装箱问题的一个近似算法
设 为装箱问题的一个α-近似算法，我们来构造染色装箱问题的一个近似算法 。
算法：
输入：L = (，，…，)及每个物件的大小 (0，1]，=1，2，…， ．每个物件的颜色N。
输出：需要的箱子数目 ．
step 1： 把物件按颜色分类为：第1类，第2类，…，第 类，并设第 类有个物件，=1，2，…，．则 =．
step 2：对第类的个物件调用一次算法，得到的箱子数目分别为 ，=1,2，…，．
step 3：输出=
定理1 设为装箱问题的一个 —近似算法，则算法 是染色装箱问题的一个—近似算法。
证明 设算法的输出值为，其问题的最优值为OPT。每一次循环中调用算法，则对于第类的个物件的输出值为，最优值为 。免费论文。于是我们得到  ，( 1)，=1，2，…．由于每个箱子中必须放相同颜色的物件，因而
 = ，=
所以
  =
因此算法是染色装箱问题的一个-近似算法。
定理2 CF算法是一维装箱问题的一个 –近似算法。
推论 在算法中，如果对每种颜色调用的算法为CF算法，那么算法是染色装箱问题的一个–近似算法。
由于算法的时间复杂度为 ，所以算法的时间复杂度为
 （  ）=（ ）=
参考文献
[1] ASSMAN S B,JOHNSON D S, KLEITMAN D J, etal. On the dual of the one-dimensional bin packingproblem [J]. J. Algorithms, 1984, 5: 502-525.
[2] 孙春玲.染色装箱问题及其启发式算法.云南大学学报(自然科学版)，第14卷第4期 2005年10月.
[3] 帅天平,王海明.箱子是在线到达的变尺寸带核装箱问题[J].应用数学学报,2004,27(3):423~429.
|
