A dynamic programming approach to solving the multiple choice knapsack problem (Q761349)

The paper deals with an algorithm based on computing knapsack functions for a multiple choice knapsack problem (MCK). The modification using the optimal solution of its linear relaxation is given and the computational complexity of the algorithm derived. First, MCK is described mathematically. A method similar to that of Gilmore and Gomory for solving 0-1 knapsack problems (KP) is given. This method is based on recursive computing of multiple choice knapsack functions. An algorithm for MCK exploiting the optimal solution of LMCK is derived and its computational complexity examined. If a heuristic solution obtained from the optimal solution is close to the optimal solution of MCK, then it may be better to apply this algorithm because of its smaller complexity. Otherwise, the general dynamic programming method for MCK may be used.