A dynamic programming method with lists for the knapsack sharing problem
In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy. (C) 2010 Elsevier Ltd. All rights reserved.
dynamic programming knapsack sharing problem combinatorial optimization max-min programming