No label defined (Q4031601)

Let (KP) denote the classical (integral) knapsack problem maximize \(\sum^ m_{j=1} p_ j z_ j\) subject to \(\sum^ m_{j=1} w_ j z_ j\leq c\), \(z_ j\geq 0\) and integer, \(j=1,\dots,m\), for given \(p_ j\), \(z_ j\), \(j=1,\dots,m\), and given \(c\). The aim of this paper is to show how the solution of (KP) by dynamic programming can be implemented on a systolic array. First, a non-modular solution is presented under the assumption that the cells' memory size \(\alpha\) may depend upon the problem size \((\alpha\geq c)\). The time for finding the optimal value of (KP) will be \(2m+c\). In a second, modular, case each celle has an adressable memory of size \(\alpha\), which is independent of the problem size. \(\lceil mc/\alpha\) cells are required to store the problem's data and \(c+\lceil mc/\alpha+m\) time units are necessary for finding (KP)'s optimal value. Repeated use of any cell is possible under the following assumptions: (i) the array consists of unidirectional connected cells each of them with adressable memory of size \(\alpha\); (ii) a memory module receives data from the last cell and sends them to the first; (iii) any cell saves a copy of its results in a common parallel matrix memory connected to one supplementary cell. Features such as the time to obtain (KP)'s optimal value and the queue size requirements are discussed at the end.