关于染色装箱问题的一个近似算法(图文).docx

关于染色装箱问题的一个近似算法(图文).docx关于染色装箱问题的一个近似算法(图文)
论文导读：装箱问题要求把一个给定了大小的物件序列装入一些容量为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，…．由于每个箱子中必须放相同颜色的物件，因而
=，=
所以
=
因此算法是染色装箱问题的一个-近似算法。
定