### 2008-15

by Lazarev, A., Werner, F..

**Series:** 2008-15, Preprints

- MSC:
- 90C39 Dynamic programming
- 90C27 Combinatorial optimization

**Abstract:**

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

corresponding problem.

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.

**Keywords:**

Dynamic programming, Exact algorithm, Graphical algorithm, Partition problem, Knapsack problem

**This paper was published in:**

Computers and Mathematics wit