A PIPELINED ALGORITHM FOR MULTIPLE-CHOICE 0/1 KNAPSACK PROBLEM

In this paper, we first propose a dynamic programming solution to the multiple-choice 0/1 knapsack problem. Then, a pipelined algorithm based on the dynamic programming solution is derived. The pipelined architecture consists of a linear processor array, a queue, and a memory module, which are connected into a cycle. The processor array is of fixed length and can be regarded as a pipeline where the dynamic programming algorithm is implemented through pipelining.