We consider the 0-1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an ILP solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases which still permit fully polynomial time approximation schemes (FPTASs) and others where the problem remains hard to approximate.
Article
View Improved dynamic programming and approximation results for the knapsack problem with setups