Abstract: As one of the constrained bin packing problems （BPP）, coloring BPP has many important applications such as multi processor real time scheduling, etc . An approximation algorithm, called KC A , to solve the coloring BPP is proposed in this paper. It classifies the inputs first and then packs the objects in the same class with classical bin packing algorithm A . Also given are a lower bound of the worst case asymptotic performance ratio of KC A and analysis of the asymptotic worst case, average case performance ratio of the KC A algorithm when A is NF, FF, BF or WF . Finally the experimental results are given. KC FF shows a better result in the experiment.