by Lazarev, A., Werner, F..
Series: 2008-15, Preprints
In this paper we consider a graphical realization of dynamic programming.
The concept is discussed on the partition and knapsack problems.
In contrast to dynamic programming, the new algorithm can also treat problems with
non-integer data without necessary transformations of the
We compare the proposed method with existing algorithms for these problems on small-size
instances with at most 10 numbers in the partition problem. For almost all instances,
the new algorithm considers on average
substantially less stages than
the dynamic programming algorithm.
Dynamic programming, Exact algorithm, Graphical algorithm, Partition problem, Knapsack problem
This paper was published in:
Computers and Mathematics wit