Id: arxiv/2602.12214 Url: https://arxiv.org/abs/2602.12214 Tags: math.OC Score: 0 Title: The colored knapsack problem: structural properties and exact algorithms Domain: math.OC Source: arxiv Authors: Fabio Ciccarelli, Alexander Helber, Erik Mühmer Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-12 Page: https://delphi.science/r/arxiv/2602.12214 We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly NP-hard and propose two exact dynamic programming algorithms with time complexities of $\mathcal{O}(bn^4)$ and $\mathcal{O}(b^2n^3)$, respectively. To enhance practical performance, we derive various dominance and fathoming rules for both approaches. From a theoretical…