A dynamic programming approach to the multiple-choice multi-period knapsack problem and the recursive APL2 code

The multiple-choice multi-period knapsack problem lies on the interface of multiple choice programming and knapsack problems. Previous study of this problem attempted to find its optimal solution through the branch-and-bound procedure using special-ordered sets. In this paper, we propose another solution approach based on the dynamic programming to locate its optimal solution through recursive evaluation of Bellman's equation at each period. We also introduce a set of concise computer code written in IBM's APL2 that solves the problem recursively. Based on this developed APL2 codes, a computational experiment was conducted to further examine the performance of this dynamic programming solution approach.