Substantiation of a heuristic algorithm in the knapsack problem

A. A. Bosov, A. V. Gоrbоvа, N. V. Khalipova

Abstract


Introduction: Formed knapsack problem in terms of set functions and is a heuristic algorithm. The goal: to prove that the heuristic algorithm is essential. Some facts from [2]. The equivalence of the limit order to E.Borelyu and convergence in measure. The theorem about the need to set a maximum of function. The situation is quite the algorithm: We present three cases where a heuristic algorithm is sufficient. Counterexample: An Rear take from [1], and given the addition heuristic algorithm, which allows to obtain the solution of the knapsack problem. Vector optimization: With the knapsack problem is tied vector optimization of investment activities. Conclusions: The proposed algorithm for solving the knapsack problem and for additive functions algorithm for Pareto solutions of vector optimization for the two indicators. Appendix: an agenda for the Maple solutions knapsack problem.

Keywords


knapsack problem; set functions; vector optimization; the task of investing

GOST Style Citations


1. Лазарев, А. А. Теория расписаний, задачи и алгоритмы [Текст] / А. А. Лазарев, Е. Р. Гафаров. – М. : МГУ им. М. В. Ломоносова, 2011. – С. 222. 

2. Босов, А. А. Функции множества и их применение [Текст] / А. А. Босов. – Днепродзержинск: Вид. дім «Андрій», 2007. – 182 с.





Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN 2307–3489 (Print)
ІSSN 2307–6666 (Online)