Кооперативный подход к задаче о рюкзаке

Abstract

Выпускная квалификационная работа посвящена рассмотрению задачи о рюкзаке с позиции теории кооперативных игр, изучению принципа оптимизации теории кооперативных и рассмотрению классических методов решения данной задачи. Актуальность нахождения наиболее оптимального решения данной задачи, а также задач подобного класса сложно недооценить. Проведен анализ предметной области, рассмотрено большое количество научных трудов как Российских умов так и зарубежных. Рассмотрен подход к задаче с позиции кооперативных игр, а также классические подходы. Введены базовые понятия теории кооперативных игр, рассмотрен класс задач, доказано, что ядра не пустые, приведена реализация алгоритмов к классическим методам. Проведено тестирование алгоритмов на корректность работы, оценена их сложность. Алгоритмы реализованы на языке Pyhton 3.6, C++14 с использованием встроенных структур данных.