Least-cost partition algorithms (Q1823166)

The authors present three modifications of the standard \(O(n^ 2)\) dynamic programming algorithm for the knapsack problem. The first one restricts the number of possible substitutions, leading to significant average-case complexity improvement; worst-cost complexity remains \(O(n^ 2)\), but average-case complexity becomes \(O(n^{3/2})\). The second is a method of condensing partially developed solutions. The third is a prepass which eliminates some equations and guarantees O(n) or O(n log n) efficiency in a number of important special cases. Also, a related algorithm for the problem of partitioning an integer by integers not larger than some upper bound p, of complexity polynomial in p, is given.