Approximation Schemes for a Class-Constrained Knapsack Problem

We present approximation algorithms for a class-constrained version of the knapsack problem: Given an integer $K$, a set of items $S$, each item with value, size and a class, find a subset of $S$ of maximum total value such that items are grouped in compartments. Each compartment must have only items of one class and must be separated by the subsequent compartment by a wall division of size $d$. Moreover, two subsequent wall divisions must stay a distance of at least $d_{\min}$ and at most $d_{\max}$. The total size used by compartments and by wall divisions must be at most $K$. This problem have practical applications on cutting-stock problems.

2003