The Multiple Knapsack Problem with Setup (MKPS) is a combinatorial optimization problem, where its goal is to maximize the profit of a subset of selected items by adding a negative cost related to the classes containing the aforementioned selected items. Herein, we propose to approximately solve MKPS by using a hybrid algorithm, where a series of valid constraints are sequentially added to the original problem. Next, a modified version of the method is also designed for enhancing the behavior of the first hybrid algorithm. Both versions of the proposed method are computationally analyzed on benchmark instances of the literature, where their provided results were compared to those achieved by best methods available in the literature. New bounds are discovered.