Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint

Max-max, max-min, min-max and min-min optimization problems with a knapsack-type constraint containing a single numerical parameter are studied. The goal is to present optimal solutions for all possible values of the parameter. Algorithms with O (n log n) and O (n(2)) running times are proposed for the problems with a fixed parameter and for the general problem, respectively, where n is the number of items to be packed into the knapsack. The latter algorithm determines optimal solution values for all values of the parameter in O (n log(2) n) time. The problem of deciding whether there exists a single optimal solution for all values of the numerical parameter is proved to be NP-complete.