A SYSTOLIC ALGORITHM FOR SOLVING KNAPSACK-PROBLEMS

Abstract

A systolic algorithm for solving the O/1-knapsack problems with n items is presented. The computational model used is a tree structure which consists of 2(n) identical processing elements (PEs). Each PE executes the same program at any time step. The time complexity varies from n to 3n - 2 steps which includes all the input/output data communication time. The design process and the correctness verification of this algorithm are considered in detail.