In the Colored Bin Packing problem a set of items with varying weights and colors must be packed into bins of uniform weight limit such that no two items of the same color may be packed adjacently within a bin. We solve this problem for the case where there are two or more colors when the items have zero weight and when the items have unit weight. Our algorithms are optimal and run in linear time. Since our algorithms apply for two or more colors, they demonstrate that the problem does not get harder as the number of colors increases. We also provide closed-form expressions for the optimal number of bins.
explored a zero-weight version of the 2-color variant of this problem @cite_0 . They show that in this case, the optimal number of bins equals the color - the absolute difference between the number of items of the two colors. The paper's main result is an optimal algorithm, named Balancing Any Fit, which operates on the simple principle that an item should be packed in an available bin containing the most oppositely-colored items. This is made easier since weight is not an issue.
@cite_0
1781979225
In the Colored Bin Packing problem a sequence of items of sizes up to (1 ) arrives to be packed into bins of unit capacity. Each item has one of (c 2 ) colors and an additional constraint is that we cannot pack two items of the same color next to each other in the same bin. The objective is to minimize the number of bins.