Аннотация:We consider a modification of dynamic programming algorithm
(DPA), which is called as graphical algorithm (GA). For the knapsack
problem (KP) it is shown that the time complexity of GA is less
than the time complexity of DPA. Moreover, the running time of GA
is often essentially reduced. GA can also solve big scale instances and
instances, where the parameters are not only positive integer. The paper
outlines different methods of parallelizing GA taking into account its
main features and advantages to various parallel architectures, in particular
by using OpenCL and MPI framework. Experiments show that
"hard" instances of KP for GA have correlation pj kwj for all j, where
pj and wj are utility and capacity of item j = 1, 2, . . . , n.